Added IterableList<HP> support to MichaelSet
authorkhizmax <libcds.dev@gmail.com>
Thu, 4 Aug 2016 21:04:19 +0000 (00:04 +0300)
committerkhizmax <libcds.dev@gmail.com>
Thu, 4 Aug 2016 21:04:19 +0000 (00:04 +0300)
25 files changed:
cds/container/details/iterable_list_base.h
cds/container/details/michael_set_base.h
cds/container/impl/iterable_list.h
cds/container/impl/lazy_list.h
cds/container/impl/michael_list.h
cds/container/lazy_list_nogc.h
cds/container/michael_list_nogc.h
cds/container/michael_set.h
cds/container/michael_set_nogc.h
cds/intrusive/michael_set.h
projects/Win/vc14/gtest-set.vcxproj
projects/Win/vc14/gtest-set.vcxproj.filters
test/unit/set/CMakeLists.txt
test/unit/set/michael_iterable_dhp.cpp [new file with mode: 0644]
test/unit/set/michael_iterable_hp.cpp [new file with mode: 0644]
test/unit/set/michael_lazy_dhp.cpp
test/unit/set/michael_lazy_hp.cpp
test/unit/set/michael_lazy_nogc.cpp
test/unit/set/michael_michael_dhp.cpp
test/unit/set/michael_michael_hp.cpp
test/unit/set/michael_michael_nogc.cpp
test/unit/set/test_michael_iterable.h [new file with mode: 0644]
test/unit/set/test_michael_iterable_hp.h [new file with mode: 0644]
test/unit/set/test_set.h
test/unit/set/test_set_data.h [new file with mode: 0644]

index 2adc1aa..2d6e9fb 100644 (file)
@@ -158,6 +158,31 @@ namespace cds { namespace container {
     struct iterable_list_tag
     {};
 
+    //@cond
+    template <typename List>
+    struct is_iterable_list {
+        enum {
+            value = false
+        };
+    };
+
+    template <typename GC, typename T, typename Traits>
+    struct is_iterable_list< IterableList<GC, T, Traits >>
+    {
+        enum {
+            value = true
+        };
+    };
+
+    template <typename GC, typename T, typename Traits>
+    struct is_iterable_list< IterableKVList<GC, T, Traits >>
+    {
+        enum {
+            value = true
+        };
+    };
+    //@endcond
+
 }}  // namespace cds::container
 
 
index 0db930c..bd7543f 100644 (file)
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_CONTAINER_DETAILS_MICHAEL_SET_BASE_H
index cac200e..228e96a 100644 (file)
@@ -139,6 +139,22 @@ namespace cds { namespace container {
 
         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 
+        //@cond
+        // Rebind traits (split-list support)
+        template <typename... Options>
+        struct rebind_traits {
+            typedef IterableList<
+                gc
+                , value_type
+                , typename cds::opt::make_options< traits, Options...>::type
+            > type;
+        };
+
+        // Stat selector
+        template <typename Stat>
+        using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
+        //@endcond
+
     protected:
         //@cond
         typedef typename maker::cxx_data_allocator   cxx_data_allocator;
@@ -750,12 +766,6 @@ namespace cds { namespace container {
 
     protected:
         //@cond
-        //template <typename Q>
-        //static value_type* alloc_data( Q const& v )
-        //{
-        //    return cxx_data_allocator().New( v );
-        //}
-
         template <typename... Args>
         static value_type* alloc_data( Args&&... args )
         {
index 6b7efb5..496f1b5 100644 (file)
@@ -144,6 +144,22 @@ namespace cds { namespace container {
 
         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 
+        //@cond
+        // Rebind traits (split-list support)
+        template <typename... Options>
+        struct rebind_traits {
+            typedef LazyList<
+                gc
+                , value_type
+                , typename cds::opt::make_options< traits, Options...>::type
+            > type;
+        };
+
+        // Stat selector
+        template <typename Stat>
+        using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
+        //@endcond
+
     protected:
         //@cond
         typedef typename base_class::value_type   node_type;
@@ -152,40 +168,6 @@ namespace cds { namespace container {
         typedef typename maker::intrusive_traits::compare  intrusive_key_comparator;
 
         typedef typename base_class::node_type head_type;
-        //@endcond
-
-    public:
-        /// Guarded pointer
-        typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
-
-    protected:
-        //@cond
-        static value_type& node_to_value( node_type& n )
-        {
-            return n.m_Value;
-        }
-
-        static value_type const& node_to_value( node_type const& n )
-        {
-            return n.m_Value;
-        }
-
-        template <typename Q>
-        static node_type * alloc_node( Q const& v )
-        {
-            return cxx_allocator().New( v );
-        }
-
-        template <typename... Args>
-        static node_type * alloc_node( Args&&... args )
-        {
-            return cxx_allocator().MoveNew( std::forward<Args>(args)... );
-        }
-
-        static void free_node( node_type * pNode )
-        {
-            cxx_allocator().Delete( pNode );
-        }
 
         struct node_disposer {
             void operator()( node_type * pNode )
@@ -193,35 +175,20 @@ namespace cds { namespace container {
                 free_node( pNode );
             }
         };
-        typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
+        typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
 
-        head_type& head()
-        {
-            return base_class::m_Head;
-        }
-
-        head_type const& head() const
-        {
-            return base_class::m_Head;
-        }
-
-        head_type& tail()
-        {
-            return base_class::m_Tail;
-        }
-
-        head_type const&  tail() const
-        {
-            return base_class::m_Tail;
-        }
         //@endcond
 
+    public:
+        /// Guarded pointer
+        typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
+
     protected:
-                //@cond
+        //@cond
         template <bool IsConst>
         class iterator_type: protected base_class::template iterator_type<IsConst>
         {
-            typedef typename base_class::template iterator_type<IsConst>    iterator_base;
+            typedef typename base_class::template iterator_type<IsConst> iterator_base;
 
             iterator_type( head_type const& pNode )
                 : iterator_base( const_cast<head_type *>( &pNode ))
@@ -240,7 +207,7 @@ namespace cds { namespace container {
             iterator_type()
             {}
 
-            iterator_type( const iterator_type& src )
+            iterator_type( iterator_type const& src )
                 : iterator_base( src )
             {}
 
@@ -382,9 +349,9 @@ namespace cds { namespace container {
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename Q>
-        bool insert( Q const& val )
+        bool insert( Q&& val )
         {
-            return insert_at( head(), val );
+            return insert_at( head(), std::forward<Q>( val ));
         }
 
         /// Inserts new node
@@ -410,9 +377,9 @@ namespace cds { namespace container {
             it is preferable that the initialization should be completed only if inserting is successful.
         */
         template <typename Q, typename Func>
-        bool insert( Q const& key, Func func )
+        bool insert( Q&& key, Func func )
         {
-            return insert_at( head(), key, func );
+            return insert_at( head(), std::forward<Q>( key ), func );
         }
 
         /// Inserts data of type \p value_type constructed from \p args
@@ -436,14 +403,14 @@ namespace cds { namespace container {
             The functor \p Func signature is:
             \code
                 struct my_functor {
-                    void operator()( bool bNew, value_type& item, Q const& val );
+                    void operator()( bool bNew, value_type& item, Q const& key );
                 };
             \endcode
 
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
             - \p item - item of the list
-            - \p val - argument \p key passed into the \p %update() function
+            - \p key - argument \p key passed into the \p %update() function
 
             The functor may change non-key fields of the \p item;
             during \p func call \p item is locked so it is safe to modify the item in
@@ -768,6 +735,53 @@ namespace cds { namespace container {
 
     protected:
         //@cond
+        static value_type& node_to_value( node_type& n )
+        {
+            return n.m_Value;
+        }
+
+        static value_type const& node_to_value( node_type const& n )
+        {
+            return n.m_Value;
+        }
+
+        template <typename Q>
+        static node_type * alloc_node( Q const& v )
+        {
+            return cxx_allocator().New( v );
+        }
+
+        template <typename... Args>
+        static node_type * alloc_node( Args&&... args )
+        {
+            return cxx_allocator().MoveNew( std::forward<Args>( args )... );
+        }
+
+        static void free_node( node_type * pNode )
+        {
+            cxx_allocator().Delete( pNode );
+        }
+
+        head_type& head()
+        {
+            return base_class::m_Head;
+        }
+
+        head_type const& head() const
+        {
+            return base_class::m_Head;
+        }
+
+        head_type& tail()
+        {
+            return base_class::m_Tail;
+        }
+
+        head_type const&  tail() const
+        {
+            return base_class::m_Tail;
+        }
+
         bool insert_node( node_type * pNode )
         {
             return insert_node_at( head(), pNode );
@@ -787,9 +801,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q>
-        bool insert_at( head_type& refHead, const Q& val )
+        bool insert_at( head_type& refHead, Q&& val )
         {
-            return insert_node_at( refHead, alloc_node( val ));
+            return insert_node_at( refHead, alloc_node( std::forward<Q>( val )));
         }
 
         template <typename... Args>
@@ -799,9 +813,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Func>
-        bool insert_at( head_type& refHead, const Q& key, Func f )
+        bool insert_at( head_type& refHead, Q&& key, Func f )
         {
-            scoped_node_ptr pNode( alloc_node( key ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( key )));
 
             if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node_to_value(node) ); } )) {
                 pNode.release();
@@ -811,7 +825,7 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare, typename Func>
-        bool erase_at( head_type& refHead, const Q& key, Compare cmp, Func f )
+        bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
         {
             return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ f( node_to_value(node) ); } );
         }
@@ -823,12 +837,12 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Func>
-        std::pair<bool, bool> update_at( head_type& refHead, const Q& key, Func f, bool bAllowInsert )
+        std::pair<bool, bool> update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert )
         {
             scoped_node_ptr pNode( alloc_node( key ));
 
             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
-                [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(node), key );},
+                [&f, &key](bool bNew, node_type& node, node_type&) { f( bNew, node_to_value(node), key );},
                 bAllowInsert );
             if ( ret.first && ret.second )
                 pNode.release();
index 27c87b9..97e438a 100644 (file)
@@ -140,6 +140,22 @@ namespace cds { namespace container {
 
         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 
+        //@cond
+        // Rebind traits (split-list support)
+        template <typename... Options>
+        struct rebind_traits {
+            typedef MichaelList<
+                gc
+                , value_type
+                , typename cds::opt::make_options< traits, Options...>::type
+            > type;
+        };
+
+        // Stat selector
+        template <typename Stat>
+        using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
+        //@endcond
+
     protected:
         //@cond
         typedef typename base_class::value_type      node_type;
@@ -148,39 +164,6 @@ namespace cds { namespace container {
         typedef typename maker::intrusive_traits::compare intrusive_key_comparator;
 
         typedef typename base_class::atomic_node_ptr head_type;
-        //@endcond
-
-    public:
-        /// Guarded pointer
-        typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
-
-    protected:
-        //@cond
-        static value_type& node_to_value( node_type& n )
-        {
-            return n.m_Value;
-        }
-        static value_type const& node_to_value( node_type const& n )
-        {
-            return n.m_Value;
-        }
-
-        template <typename Q>
-        static node_type * alloc_node( Q const& v )
-        {
-            return cxx_allocator().New( v );
-        }
-
-        template <typename... Args>
-        static node_type * alloc_node( Args&&... args )
-        {
-            return cxx_allocator().MoveNew( std::forward<Args>(args)... );
-        }
-
-        static void free_node( node_type * pNode )
-        {
-            cxx_allocator().Delete( pNode );
-        }
 
         struct node_disposer {
             void operator()( node_type * pNode )
@@ -189,18 +172,12 @@ namespace cds { namespace container {
             }
         };
         typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
-
-        head_type& head()
-        {
-            return base_class::m_pHead;
-        }
-
-        head_type const& head() const
-        {
-            return base_class::m_pHead;
-        }
         //@endcond
 
+    public:
+        /// Guarded pointer
+        typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
+
     protected:
         //@cond
         template <bool IsConst>
@@ -364,9 +341,9 @@ namespace cds { namespace container {
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename Q>
-        bool insert( Q const& val )
+        bool insert( Q&& val )
         {
-            return insert_at( head(), val );
+            return insert_at( head(), std::forward<Q>( val ));
         }
 
         /// Inserts new node
@@ -394,9 +371,9 @@ namespace cds { namespace container {
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename Q, typename Func>
-        bool insert( Q const& key, Func func )
+        bool insert( Q&& key, Func func )
         {
-            return insert_at( head(), key, func );
+            return insert_at( head(), std::forward<Q>(key), func );
         }
 
         /// Updates data by \p key
@@ -410,14 +387,14 @@ namespace cds { namespace container {
             The functor \p Func signature is:
             \code
                 struct my_functor {
-                    void operator()( bool bNew, value_type& item, Q const& val );
+                    void operator()( bool bNew, value_type& item, Q const& key );
                 };
             \endcode
 
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
             - \p item - item of the list
-            - \p val - argument \p key passed into the \p %update() function
+            - \p key - argument \p key passed into the \p %update() function
 
             The functor may change non-key fields of the \p item; however, \p func must guarantee
             that during changing no any other modifications could be made on this item by concurrent threads.
@@ -665,7 +642,7 @@ namespace cds { namespace container {
         //@endcond
 
         /// Finds \p key and return the item found
-        /** \anchor cds_nonintrusive_MichaelList_hp_get
+        /**
             The function searches the item with key equal to \p key
             and returns it as \p guarded_ptr.
             If \p key is not found the function returns an empty guarded pointer.
@@ -700,7 +677,7 @@ namespace cds { namespace container {
 
         /// Finds \p key and return the item found
         /**
-            The function is an analog of \ref cds_nonintrusive_MichaelList_hp_get "get( Q const&)"
+            The function is an analog of \p get( Q const&)
             but \p pred is used for comparing the keys.
 
             \p Less functor has the semantics like \p std::less but should accept arguments of type \p value_type and \p Q
@@ -749,6 +726,42 @@ namespace cds { namespace container {
 
     protected:
         //@cond
+        static value_type& node_to_value( node_type& n )
+        {
+            return n.m_Value;
+        }
+        static value_type const& node_to_value( node_type const& n )
+        {
+            return n.m_Value;
+        }
+
+        template <typename Q>
+        static node_type * alloc_node( Q const& v )
+        {
+            return cxx_allocator().New( v );
+        }
+
+        template <typename... Args>
+        static node_type * alloc_node( Args&&... args )
+        {
+            return cxx_allocator().MoveNew( std::forward<Args>( args )... );
+        }
+
+        static void free_node( node_type * pNode )
+        {
+            cxx_allocator().Delete( pNode );
+        }
+
+        head_type& head()
+        {
+            return base_class::m_pHead;
+        }
+
+        head_type const& head() const
+        {
+            return base_class::m_pHead;
+        }
+
         bool insert_node( node_type * pNode )
         {
             return insert_node_at( head(), pNode );
@@ -767,15 +780,15 @@ namespace cds { namespace container {
         }
 
         template <typename Q>
-        bool insert_at( head_type& refHead, Q const& val )
+        bool insert_at( head_type& refHead, Q&& val )
         {
-            return insert_node_at( refHead, alloc_node( val ));
+            return insert_node_at( refHead, alloc_node( std::forward<Q>(val)));
         }
 
         template <typename Q, typename Func>
-        bool insert_at( head_type& refHead, Q const& key, Func f )
+        bool insert_at( head_type& refHead, Q&& key, Func f )
         {
-            scoped_node_ptr pNode( alloc_node( key ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( key )));
 
             if ( base_class::insert_at( refHead, *pNode, [&f]( node_type& node ) { f( node_to_value(node) ); } )) {
                 pNode.release();
index 4227d8b..5655b80 100644 (file)
@@ -86,6 +86,22 @@ namespace cds { namespace container {
 
         static CDS_CONSTEXPR bool const c_bSort = base_class::c_bSort; ///< List type: ordered (\p true) or unordered (\p false)
 
+        //@cond
+        // Rebind traits (split-list support)
+        template <typename... Options>
+        struct rebind_traits {
+            typedef LazyList<
+                gc
+                , value_type
+                , typename cds::opt::make_options< traits, Options...>::type
+            > type;
+        };
+
+        // Stat selector
+        template <typename Stat>
+        using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
+        //@endcond
+
     protected:
         //@cond
         typedef typename base_class::value_type     node_type;
@@ -94,35 +110,6 @@ namespace cds { namespace container {
         typedef typename base_class::key_comparator intrusive_key_comparator;
 
         typedef typename base_class::node_type      head_type;
-        //@endcond
-
-    protected:
-        //@cond
-        static value_type& node_to_value( node_type& n )
-        {
-            return n.m_Value;
-        }
-
-        static node_type * alloc_node()
-        {
-            return cxx_allocator().New();
-        }
-
-        static node_type * alloc_node( value_type const& v )
-        {
-            return cxx_allocator().New( v );
-        }
-
-        template <typename... Args>
-        static node_type * alloc_node( Args&&... args )
-        {
-            return cxx_allocator().MoveNew( std::forward<Args>(args)... );
-        }
-
-        static void free_node( node_type * pNode )
-        {
-            cxx_allocator().Delete( pNode );
-        }
 
         struct node_disposer {
             void operator()( node_type * pNode )
@@ -131,26 +118,6 @@ namespace cds { namespace container {
             }
         };
         typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
-
-        head_type& head()
-        {
-            return base_class::m_Head;
-        }
-
-        head_type const& head() const
-        {
-            return base_class::m_Head;
-        }
-
-        head_type& tail()
-        {
-            return base_class::m_Tail;
-        }
-
-        head_type const& tail() const
-        {
-            return base_class::m_Tail;
-        }
         //@endcond
 
     protected:
@@ -290,16 +257,6 @@ namespace cds { namespace container {
         }
     //@}
 
-    protected:
-        //@cond
-        iterator node_to_iterator( node_type * pNode )
-        {
-            if ( pNode )
-                return iterator( *pNode );
-            return end();
-        }
-        //@endcond
-
     public:
         /// Default constructor
         LazyList()
@@ -326,9 +283,9 @@ namespace cds { namespace container {
             Return an iterator pointing to inserted item if success \ref end() otherwise
         */
         template <typename Q>
-        iterator insert( Q const& val )
+        iterator insert( Q&& val )
         {
-            return node_to_iterator( insert_at( head(), val ) );
+            return node_to_iterator( insert_at( head(), std::forward<Q>( val )) );
         }
 
         /// Inserts data of type \p value_type created from \p args
@@ -344,7 +301,6 @@ namespace cds { namespace container {
         /// Updates the item
         /**
             If \p key is not in the list and \p bAllowInsert is \p true,
-
             the function inserts a new item.
             Otherwise, the function returns an iterator pointing to the item found.
 
@@ -353,9 +309,9 @@ namespace cds { namespace container {
             already is in the list.
         */
         template <typename Q>
-        std::pair<iterator, bool> update( Q const& val, bool bAllowInsert = true )
+        std::pair<iterator, bool> update( Q&& val, bool bAllowInsert = true )
         {
-            std::pair< node_type *, bool > ret = update_at( head(), val, bAllowInsert );
+            std::pair< node_type *, bool > ret = update_at( head(), std::forward<Q>( val ), bAllowInsert );
             return std::make_pair( node_to_iterator( ret.first ), ret.second );
         }
         //@cond
@@ -461,6 +417,59 @@ namespace cds { namespace container {
 
     protected:
         //@cond
+        static value_type& node_to_value( node_type& n )
+        {
+            return n.m_Value;
+        }
+
+        static node_type * alloc_node()
+        {
+            return cxx_allocator().New();
+        }
+
+        static node_type * alloc_node( value_type const& v )
+        {
+            return cxx_allocator().New( v );
+        }
+
+        template <typename... Args>
+        static node_type * alloc_node( Args&&... args )
+        {
+            return cxx_allocator().MoveNew( std::forward<Args>( args )... );
+        }
+
+        static void free_node( node_type * pNode )
+        {
+            cxx_allocator().Delete( pNode );
+        }
+
+        head_type& head()
+        {
+            return base_class::m_Head;
+        }
+
+        head_type const& head() const
+        {
+            return base_class::m_Head;
+        }
+
+        head_type& tail()
+        {
+            return base_class::m_Tail;
+        }
+
+        head_type const& tail() const
+        {
+            return base_class::m_Tail;
+        }
+
+        iterator node_to_iterator( node_type * pNode )
+        {
+            if ( pNode )
+                return iterator( *pNode );
+            return end();
+        }
+
         iterator insert_node( node_type * pNode )
         {
             return node_to_iterator( insert_node_at( head(), pNode ));
@@ -477,9 +486,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q>
-        node_type * insert_at( head_type& refHead, Q const& val )
+        node_type * insert_at( head_type& refHead, Q&& val )
         {
-            return insert_node_at( refHead, alloc_node( val ));
+            return insert_node_at( refHead, alloc_node( std::forward<Q>( val )));
         }
 
         template <typename... Args>
@@ -489,13 +498,13 @@ namespace cds { namespace container {
         }
 
         template <typename Q>
-        std::pair< node_type *, bool > update_at( head_type& refHead, Q const& val, bool bAllowInsert )
+        std::pair< node_type *, bool > update_at( head_type& refHead, Q&& val, bool bAllowInsert )
         {
-            scoped_node_ptr pNode( alloc_node( val ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
             node_type * pItemFound = nullptr;
 
             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
-                [&pItemFound](bool, node_type& item, node_type&){ pItemFound = &item; },
+                [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; },
                 bAllowInsert );
 
             if ( ret.second )
index 1bf897c..4252360 100644 (file)
@@ -100,6 +100,22 @@ namespace cds { namespace container {
         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
         typedef typename base_class::stat         stat;           ///< Internal statistics
 
+        //@cond
+        // Rebind traits (split-list support)
+        template <typename... Options>
+        struct rebind_traits {
+            typedef MichaelList<
+                gc
+                , value_type
+                , typename cds::opt::make_options< traits, Options...>::type
+            > type;
+        };
+
+        // Stat selector
+        template <typename Stat>
+        using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
+        //@endcond
+
     protected:
         //@cond
         typedef typename base_class::value_type   node_type;
@@ -108,30 +124,6 @@ namespace cds { namespace container {
         typedef typename maker::intrusive_traits::compare  intrusive_key_comparator;
 
         typedef typename base_class::atomic_node_ptr head_type;
-        //@endcond
-
-    protected:
-        //@cond
-        static node_type * alloc_node()
-        {
-            return cxx_allocator().New();
-        }
-
-        static node_type * alloc_node( value_type const& v )
-        {
-            return cxx_allocator().New( v );
-        }
-
-        template <typename... Args>
-        static node_type * alloc_node( Args&&... args )
-        {
-            return cxx_allocator().MoveNew( std::forward<Args>(args)... );
-        }
-
-        static void free_node( node_type * pNode )
-        {
-            cxx_allocator().Delete( pNode );
-        }
 
         struct node_disposer {
             void operator()( node_type * pNode )
@@ -139,17 +131,8 @@ namespace cds { namespace container {
                 free_node( pNode );
             }
         };
-        typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
-
-        head_type& head()
-        {
-            return base_class::m_pHead;
-        }
 
-        head_type const& head() const
-        {
-            return base_class::m_pHead;
-        }
+        typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
         //@endcond
 
     protected:
@@ -284,16 +267,6 @@ namespace cds { namespace container {
         }
     //@}
 
-    protected:
-        //@cond
-        iterator node_to_iterator( node_type * pNode )
-        {
-            if ( pNode )
-                return iterator( *pNode );
-            return end();
-        }
-        //@endcond
-
     public:
         /// Default constructor
         /**
@@ -326,9 +299,9 @@ namespace cds { namespace container {
             Return an iterator pointing to inserted item if success \ref end() otherwise
         */
         template <typename Q>
-        iterator insert( const Q& val )
+        iterator insert( Q&& val )
         {
-            return node_to_iterator( insert_at( head(), val ) );
+            return node_to_iterator( insert_at( head(), std::forward<Q>( val )) );
         }
 
         /// Updates the item
@@ -342,9 +315,9 @@ namespace cds { namespace container {
             already is in the list.
         */
         template <typename Q>
-        std::pair<iterator, bool> update( const Q& key, bool bAllowInsert = true )
+        std::pair<iterator, bool> update( Q&& key, bool bAllowInsert = true )
         {
-            std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert );
+            std::pair< node_type *, bool > ret = update_at( head(), std::forward<Q>( key ), bAllowInsert );
             return std::make_pair( node_to_iterator( ret.first ), ret.second );
         }
         //@cond
@@ -445,6 +418,44 @@ namespace cds { namespace container {
             return n.m_Value;
         }
 
+        static node_type * alloc_node()
+        {
+            return cxx_allocator().New();
+        }
+
+        static node_type * alloc_node( value_type const& v )
+        {
+            return cxx_allocator().New( v );
+        }
+
+        template <typename... Args>
+        static node_type * alloc_node( Args&&... args )
+        {
+            return cxx_allocator().MoveNew( std::forward<Args>( args )... );
+        }
+
+        static void free_node( node_type * pNode )
+        {
+            cxx_allocator().Delete( pNode );
+        }
+
+        head_type& head()
+        {
+            return base_class::m_pHead;
+        }
+
+        head_type const& head() const
+        {
+            return base_class::m_pHead;
+        }
+
+        iterator node_to_iterator( node_type * pNode )
+        {
+            if ( pNode )
+                return iterator( *pNode );
+            return end();
+        }
+
         iterator insert_node( node_type * pNode )
         {
             return node_to_iterator( insert_node_at( head(), pNode ));
@@ -461,15 +472,15 @@ namespace cds { namespace container {
         }
 
         template <typename Q>
-        node_type * insert_at( head_type& refHead, const Q& val )
+        node_type * insert_at( head_type& refHead, Q&& val )
         {
-            return insert_node_at( refHead, alloc_node( val ));
+            return insert_node_at( refHead, alloc_node( std::forward<Q>( val )));
         }
 
         template <typename Q>
-        std::pair< node_type *, bool > update_at( head_type& refHead, const Q& val, bool bAllowInsert )
+        std::pair< node_type *, bool > update_at( head_type& refHead, Q&& val, bool bAllowInsert )
         {
-            scoped_node_ptr pNode( alloc_node( val ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
             node_type * pItemFound = nullptr;
 
             std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
@@ -492,7 +503,6 @@ namespace cds { namespace container {
         {
             return base_class::find_at( refHead, key, cmp );
         }
-
         //@endcond
     };
 }} // namespace cds::container
index b3819f6..bff1903 100644 (file)
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSLIB_CONTAINER_MICHAEL_SET_H
 #define CDSLIB_CONTAINER_MICHAEL_SET_H
 
 #include <cds/container/details/michael_set_base.h>
+#include <cds/container/details/iterable_list_base.h>
 #include <cds/details/allocator.h>
 
 namespace cds { namespace container {
@@ -52,7 +53,8 @@ namespace cds { namespace container {
         - \p GC - Garbage collector used. You may use any \ref cds_garbage_collector "Garbage collector"
             from the \p libcds library.
             Note the \p GC must be the same as the \p GC used for \p OrderedList
-        - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList.
+        - \p OrderedList - ordered list implementation used as bucket for hash set, possible implementations:
+            \p MichaelList, \p LazyList, \p IterableList.
             The ordered list implementation specifies the type \p T to be stored in the hash-set,
             the comparing functor for the type \p T and other features specific for the ordered list.
         - \p Traits - set traits, default is \p michael_set::traits.
@@ -75,7 +77,7 @@ namespace cds { namespace container {
         \code
         // Our node type
         struct Foo {
-            std::string     key_    ;   // key field
+            std::string     key_;   // key field
             // ... other fields
         };
 
@@ -98,8 +100,8 @@ namespace cds { namespace container {
         Suppose, we have the following type \p Foo that we want to store in our \p %MichaelHashSet:
         \code
         struct Foo {
-            int     nKey    ;   // key field
-            int     nVal    ;   // value field
+            int     nKey;   // key field
+            int     nVal;   // value field
         };
         \endcode
 
@@ -166,67 +168,64 @@ namespace cds { namespace container {
     class MichaelHashSet
     {
     public:
-        typedef GC          gc;          ///< Garbage collector
-        typedef OrderedList bucket_type; ///< type of ordered list used as a bucket implementation
-        typedef Traits      traits;      ///< Set traits
+        typedef GC          gc;           ///< Garbage collector
+        typedef OrderedList ordered_list; ///< type of ordered list used as a bucket implementation
+        typedef Traits      traits;       ///< Set traits
 
-        typedef typename bucket_type::value_type     value_type;     ///< type of value to be stored in the list
-        typedef typename bucket_type::key_comparator key_comparator; ///< key comparison functor
+        typedef typename ordered_list::value_type     value_type;     ///< type of value to be stored in the list
+        typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
+        typedef typename ordered_list::stat           stat;           ///< Internal statistics
 
         /// Hash functor for \ref value_type and all its derivatives that you use
         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
         typedef typename traits::item_counter item_counter; ///< Item counter type
+        typedef typename traits::allocator    allocator;    ///< Bucket table allocator
 
-        typedef typename bucket_type::guarded_ptr  guarded_ptr; ///< Guarded pointer
-        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = bucket_type::c_nHazardPtrCount; ///< Count of hazard pointer required
+        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
 
-    protected:
-        //@cond
-        class internal_bucket_type: public bucket_type
-        {
-            typedef bucket_type base_class;
-        public:
-            using base_class::node_type;
-            using base_class::alloc_node;
-            using base_class::insert_node;
-            using base_class::node_to_value;
-        };
+        // GC and OrderedList::gc must be the same
+        static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 
-        /// Bucket table allocator
-        typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator >  bucket_table_allocator;
-        //@endcond
+        // atomicity::empty_item_counter is not allowed as a item counter
+        static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
+                        "cds::atomicity::empty_item_counter is not allowed as a item counter");
 
-    protected:
-        //@cond
-        item_counter    m_ItemCounter; ///< Item counter
-        hash            m_HashFunctor; ///< Hash functor
-        internal_bucket_type *  m_Buckets;     ///< bucket table
-        //@endcond
+#ifdef CDS_DOXYGEN_INVOKED
+        /// Wrapped internal statistics for \p ordered_list
+        typedef implementatin_specific bucket_stat;
+#else
+        typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
+#endif
+
+#ifdef CDS_DOXYGEN_INVOKED
+        /// Internal bucket type - rebind \p ordered_list with empty item counter and wrapped internal statistics
+        typedef modified_ordered_list internal_bucket_type;
+#else
+        typedef typename ordered_list::template rebind_traits<
+            cds::opt::item_counter< cds::atomicity::empty_item_counter >
+            , cds::opt::stat< typename bucket_stat::wrapped_stat >
+        >::type internal_bucket_type;
+#endif
+
+        /// Guarded pointer - a result of \p get() and \p extract() functions
+        typedef typename internal_bucket_type::guarded_ptr guarded_ptr;
 
-    private:
         //@cond
-        const size_t    m_nHashBitmask;
+        /// Bucket table allocator
+        typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
         //@endcond
 
     protected:
         //@cond
-        /// Calculates hash value of \p key
-        template <typename Q>
-        size_t hash_value( Q const& key ) const
-        {
-            return m_HashFunctor( key ) & m_nHashBitmask;
-        }
-
-        /// Returns the bucket (ordered list) for \p key
-        template <typename Q>
-        internal_bucket_type&    bucket( Q const& key )
-        {
-            return m_Buckets[ hash_value( key ) ];
-        }
+        size_t const           m_nHashBitmask;
+        internal_bucket_type * m_Buckets;     ///< bucket table
+        item_counter           m_ItemCounter; ///< Item counter
+        hash                   m_HashFunctor; ///< Hash functor
+        typename bucket_stat::stat  m_Stat;   ///< Internal statistics
         //@endcond
 
     public:
-    ///@name Forward iterators (only for debugging purpose)
+    ///@name Forward iterators
     //@{
         /// Forward iterator
         /**
@@ -236,11 +235,14 @@ namespace cds { namespace container {
               For some GC (like as \p gc::HP), a guard is a limited resource per thread, so an exception (or assertion) "no free guard"
               may be thrown if the limit of guard count per thread is exceeded.
             - The iterator cannot be moved across thread boundary because it contains thread-private GC's guard.
-            - Iterator ensures thread-safety even if you delete the item the iterator points to. However, in case of concurrent
-              deleting operations there is no guarantee that you iterate all item in the set. 
-              Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 
-            @warning Use this iterator on the concurrent container for debugging purpose only.
+            Iterator thread safety depends on type of \p OrderedList:
+            - for \p MichaelList and \p LazyList: iterator guarantees safety even if you delete the item that iterator points to
+              because that item is guarded by hazard pointer.
+              However, in case of concurrent deleting operations it is no guarantee that you iterate all item in the set.
+              Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
+              Use this iterator on the concurrent container for debugging purpose only.
+            - for \p IterableList: iterator is thread-safe. You may use it freely in concurrent environment.
 
             The iterator interface:
             \code
@@ -272,10 +274,10 @@ namespace cds { namespace container {
         */
 
         /// Forward iterator
-        typedef michael_set::details::iterator< bucket_type, false >    iterator;
+        typedef michael_set::details::iterator< internal_bucket_type, false > iterator;
 
         /// Const forward iterator
-        typedef michael_set::details::iterator< bucket_type, true >     const_iterator;
+        typedef michael_set::details::iterator< internal_bucket_type, true > const_iterator;
 
         /// Returns a forward iterator addressing the first element in a set
         /**
@@ -283,7 +285,7 @@ namespace cds { namespace container {
         */
         iterator begin()
         {
-            return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
+            return iterator( bucket_begin()->begin(), bucket_begin(), bucket_end());
         }
 
         /// Returns an iterator that addresses the location succeeding the last element in a set
@@ -294,7 +296,7 @@ namespace cds { namespace container {
         */
         iterator end()
         {
-            return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
+            return iterator( bucket_end()[-1].end(), bucket_end() - 1, bucket_end());
         }
 
         /// Returns a forward const iterator addressing the first element in a set
@@ -322,21 +324,9 @@ namespace cds { namespace container {
         }
     //@}
 
-    private:
-        //@cond
-        const_iterator get_const_begin() const
-        {
-            return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
-        }
-        const_iterator get_const_end() const
-        {
-            return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
-        }
-        //@endcond
-
     public:
         /// Initialize hash set
-        /** @anchor cds_nonintrusive_MichaelHashSet_hp_ctor
+        /**
             The Michael's hash set is non-expandable container. You should point the average count of items \p nMaxItemCount
             when you create an object.
             \p nLoadFactor parameter defines average count of items per bucket and it should be small number between 1 and 10.
@@ -348,22 +338,20 @@ namespace cds { namespace container {
             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
+          , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
         {
-            // GC and OrderedList::gc must be the same
-            static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
-
-            // atomicity::empty_item_counter is not allowed as a item counter
-            static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
-                           "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
-            m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
+            for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+                construct_bucket<bucket_stat>( it );
         }
 
         /// Clears hash set and destroys it
         ~MichaelHashSet()
         {
             clear();
-            bucket_table_allocator().Delete( m_Buckets, bucket_count() );
+
+            for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+                it->~internal_bucket_type();
+            bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
         }
 
         /// Inserts new node
@@ -378,9 +366,9 @@ namespace cds { namespace container {
             Returns \p true if \p val is inserted into the set, \p false otherwise.
         */
         template <typename Q>
-        bool insert( Q const& val )
+        bool insert( Q&& val )
         {
-            const bool bRet = bucket( val ).insert( val );
+            const bool bRet = bucket( val ).insert( std::forward<Q>( val ));
             if ( bRet )
                 ++m_ItemCounter;
             return bRet;
@@ -400,14 +388,15 @@ namespace cds { namespace container {
             where \p val is the item inserted.
             The user-defined functor is called only if the inserting is success.
 
-            @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
+            @warning For \ref cds_nonintrusive_MichaelList_gc "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList" 
+            as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
             @ref cds_nonintrusive_LazyList_gc "LazyList" provides exclusive access to inserted item and does not require any node-level
             synchronization.
         */
         template <typename Q, typename Func>
-        bool insert( Q const& val, Func f )
+        bool insert( Q&& val, Func f )
         {
-            const bool bRet = bucket( val ).insert( val, f );
+            const bool bRet = bucket( val ).insert( std::forward<Q>( val ), f );
             if ( bRet )
                 ++m_ItemCounter;
             return bRet;
@@ -419,7 +408,10 @@ namespace cds { namespace container {
 
             If the item \p val not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
             Otherwise, the functor \p func is called with item found.
-            The functor signature is:
+
+            The functor \p func signature depends of \p OrderedList:
+
+            <b>for \p MichaelList, \p LazyList</b>
             \code
                 struct functor {
                     void operator()( bool bNew, value_type& item, Q const& val );
@@ -432,18 +424,27 @@ namespace cds { namespace container {
 
             The functor may change non-key fields of the \p item.
 
-            Returns <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
+            <b>for \p IterableList</b>
+            \code
+                void func( value_type& val, value_type * old );
+            \endcode
+            where
+            - \p val - a new data constructed from \p key
+            - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
+
+            @return <tt> std::pair<bool, bool> </tt> where \p first is \p true if operation is successful,
             \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.
 
-            @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
+            @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" and \ref cds_nonintrusive_IterableList_gc "IterableList"
+            as the bucket see \ref cds_intrusive_item_creating "insert item troubleshooting".
             \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
             synchronization.
         */
         template <typename Q, typename Func>
-        std::pair<bool, bool> update( const Q& val, Func func, bool bAllowUpdate = true )
+        std::pair<bool, bool> update( Q&& val, Func func, bool bAllowUpdate = true )
         {
-            std::pair<bool, bool> bRet = bucket( val ).update( val, func, bAllowUpdate );
+            std::pair<bool, bool> bRet = bucket( val ).update( std::forward<Q>( val ), func, bAllowUpdate );
             if ( bRet.second )
                 ++m_ItemCounter;
             return bRet;
@@ -457,6 +458,35 @@ namespace cds { namespace container {
         }
         //@endcond
 
+        /// Inserts or updates the node (only for \p IterableList)
+        /**
+            The operation performs inserting or changing data with lock-free manner.
+
+            If the item \p val is not found in the set, then \p val is inserted iff \p bAllowInsert is \p true.
+            Otherwise, the current element is changed to \p val, the old element will be retired later
+            by call \p Traits::disposer.
+
+            Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+            \p second is \p true if \p val has been added or \p false if the item with that key
+            already in the set.
+        */
+        template <typename Q>
+#ifdef CDS_DOXYGEN_INVOKED
+        std::pair<bool, bool>
+#else
+        typename std::enable_if< 
+            std::is_same< Q, Q>::value && is_iterable_list< ordered_list >::value,
+            std::pair<bool, bool>
+        >::type
+#endif
+        upsert( Q&& val, bool bAllowInsert = true )
+        {
+            std::pair<bool, bool> bRet = bucket( val ).upsert( std::forward<Q>( val ), bAllowInsert );
+            if ( bRet.second )
+                ++m_ItemCounter;
+            return bRet;
+        }
+
         /// Inserts data of type \p value_type constructed from \p args
         /**
             Returns \p true if inserting successful, \p false otherwise.
@@ -464,22 +494,20 @@ namespace cds { namespace container {
         template <typename... Args>
         bool emplace( Args&&... args )
         {
-            typename internal_bucket_type::node_type * pNode = internal_bucket_type::alloc_node( std::forward<Args>( args )... );
-            bool bRet = bucket( internal_bucket_type::node_to_value( *pNode )).insert_node( pNode );
+            bool bRet = bucket_emplace<internal_bucket_type>( std::forward<Args>(args)... );
             if ( bRet )
                 ++m_ItemCounter;
             return bRet;
         }
 
         /// Deletes \p key from the set
-        /** \anchor cds_nonintrusive_MichaelSet_erase_val
-
-            Since the key of MichaelHashSet's item type \ref value_type is not explicitly specified,
+        /**
+            Since the key of MichaelHashSet's item type \p value_type is not explicitly specified,
             template parameter \p Q defines the key type searching in the list.
             The set item comparator should be able to compare the type \p value_type
             and the type \p Q.
 
-            Return \p true if key is found and deleted, \p false otherwise
+            Return \p true if key is found and deleted, \p false otherwise.
         */
         template <typename Q>
         bool erase( Q const& key )
@@ -492,8 +520,7 @@ namespace cds { namespace container {
 
         /// Deletes the item from the set using \p pred predicate for searching
         /**
-            The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_val "erase(Q const&)"
-            but \p pred is used for key comparing.
+            The function is an analog of \p erase(Q const&) but \p pred is used for key comparing.
             \p Less functor has the interface like \p std::less.
             \p Less must imply the same element order as the comparator used for building the set.
         */
@@ -507,8 +534,7 @@ namespace cds { namespace container {
         }
 
         /// Deletes \p key from the set
-        /** \anchor cds_nonintrusive_MichaelSet_erase_func
-
+        /**
             The function searches an item with key \p key, calls \p f functor
             and deletes the item. If \p key is not found, the functor is not called.
 
@@ -538,8 +564,7 @@ namespace cds { namespace container {
 
         /// Deletes the item from the set using \p pred predicate for searching
         /**
-            The function is an analog of \ref cds_nonintrusive_MichaelSet_erase_func "erase(Q const&, Func)"
-            but \p pred is used for key comparing.
+            The function is an analog of \p erase(Q const&, Func) but \p pred is used for key comparing.
             \p Less functor has the interface like \p std::less.
             \p Less must imply the same element order as the comparator used for building the set.
         */
@@ -569,7 +594,7 @@ namespace cds { namespace container {
             michael_set theSet;
             // ...
             {
-                michael_set::guarded_ptr gp( theSet.extract( 5 ));
+                typename michael_set::guarded_ptr gp( theSet.extract( 5 ));
                 if ( gp ) {
                     // Deal with gp
                     // ...
@@ -589,11 +614,11 @@ namespace cds { namespace container {
 
         /// Extracts the item using compare functor \p pred
         /**
-            The function is an analog of \ref cds_nonintrusive_MichaelHashSet_hp_extract "extract(Q const&)"
+            The function is an analog of \p extract(Q const&)
             but \p pred predicate is used for key comparing.
 
-            \p Less functor has the semantics like \p std::less but should take arguments of type \ref value_type and \p Q
-            in any order.
+            \p Less functor has the semantics like \p std::less but should take arguments
+            of type \p value_type and \p Q in any order.
             \p pred must imply the same element order as the comparator used for building the set.
         */
         template <typename Q, typename Less>
@@ -606,8 +631,7 @@ namespace cds { namespace container {
         }
 
         /// Finds the key \p key
-        /** \anchor cds_nonintrusive_MichaelSet_find_func
-
+        /**
             The function searches the item with key equal to \p key and calls the functor \p f for item found.
             The interface of \p Func functor is:
             \code
@@ -643,10 +667,42 @@ namespace cds { namespace container {
         }
         //@endcond
 
+        /// Finds \p key and returns iterator pointed to the item found (only for \p IterableList)
+        /**
+            If \p key is not found the function returns \p end().
+
+            @note This function is supported only for the set based on \p IterableList
+        */
+        template <typename Q>
+#ifdef CDS_DOXYGEN_INVOKED
+        iterator
+#else
+        typename std::enable_if< std::is_same<Q,Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+        find( Q& key )
+        {
+            internal_bucket_type& b = bucket( key );
+            typename internal_bucket_type::iterator it = b.find( key );
+            if ( it == b.end() )
+                return end();
+            return iterator( it, &b, bucket_end());
+        }
+        //@cond
+        template <typename Q>
+        typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+        find( Q const& key )
+        {
+            internal_bucket_type& b = bucket( key );
+            typename internal_bucket_type::iterator it = b.find( key );
+            if ( it == b.end() )
+                return end();
+            return iterator( it, &b, bucket_end() );
+        }
+        //@endcond
+
         /// Finds the key \p key using \p pred predicate for searching
         /**
-            The function is an analog of \ref cds_nonintrusive_MichaelSet_find_func "find(Q&, Func)"
-            but \p pred is used for key comparing.
+            The function is an analog of \p find(Q&, Func) but \p pred is used for key comparing.
             \p Less functor has the interface like \p std::less.
             \p Less must imply the same element order as the comparator used for building the set.
         */
@@ -663,9 +719,45 @@ namespace cds { namespace container {
         }
         //@endcond
 
-        /// Checks whether the set contains \p key
+        /// Finds \p key using \p pred predicate and returns iterator pointed to the item found (only for \p IterableList)
         /**
+            The function is an analog of \p find(Q&) but \p pred is used for key comparing.
+            \p Less functor has the interface like \p std::less.
+            \p pred must imply the same element order as the comparator used for building the set.
+
+            If \p key is not found the function returns \p end().
 
+            @note This function is supported only for the set based on \p IterableList
+        */
+        template <typename Q, typename Less>
+#ifdef CDS_DOXYGEN_INVOKED
+        iterator
+#else
+        typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+#endif
+        find_with( Q& key, Less pred )
+        {
+            internal_bucket_type& b = bucket( key );
+            typename internal_bucket_type::iterator it = b.find_with( key, pred );
+            if ( it == b.end() )
+                return end();
+            return iterator( it, &b, bucket_end() );
+        }
+        //@cond
+        template <typename Q, typename Less>
+        typename std::enable_if< std::is_same<Q, Q>::value && is_iterable_list< ordered_list >::value, iterator >::type
+        find_with( Q const& key, Less pred )
+        {
+            internal_bucket_type& b = bucket( key );
+            typename internal_bucket_type::iterator it = b.find_with( key, pred );
+            if ( it == b.end() )
+                return end();
+            return iterator( it, &b, bucket_end() );
+        }
+        //@endcond
+
+        /// Checks whether the set contains \p key
+        /**
             The function searches the item with key equal to \p key
             and returns \p true if the key is found, and \p false otherwise.
 
@@ -677,14 +769,6 @@ namespace cds { namespace container {
         {
             return bucket( key ).contains( key );
         }
-        //@cond
-        template <typename Q>
-        CDS_DEPRECATED("use contains()")
-        bool find( Q const& key )
-        {
-            return contains( key );
-        }
-        //@endcond
 
         /// Checks whether the set contains \p key using \p pred predicate for searching
         /**
@@ -697,14 +781,6 @@ namespace cds { namespace container {
         {
             return bucket( key ).contains( key, pred );
         }
-        //@cond
-        template <typename Q, typename Less>
-        CDS_DEPRECATED("use contains()")
-        bool find_with( Q const& key, Less pred )
-        {
-            return contains( key, pred );
-        }
-        //@endcond
 
         /// Finds the key \p key and return the item found
         /** \anchor cds_nonintrusive_MichaelHashSet_hp_get
@@ -720,7 +796,7 @@ namespace cds { namespace container {
             michael_set theSet;
             // ...
             {
-                michael_set::guarded_ptr gp( theSet.get( 5 ));
+                typename michael_set::guarded_ptr gp( theSet.get( 5 ));
                 if ( gp ) {
                     // Deal with gp
                     //...
@@ -785,6 +861,12 @@ namespace cds { namespace container {
             return m_ItemCounter;
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return m_Stat;
+        }
+
         /// Returns the size of hash table
         /**
             Since MichaelHashSet cannot dynamically extend the hash table size,
@@ -795,6 +877,95 @@ namespace cds { namespace container {
         {
             return m_nHashBitmask + 1;
         }
+
+    protected:
+        //@cond
+        /// Calculates hash value of \p key
+        template <typename Q>
+        size_t hash_value( Q const& key ) const
+        {
+            return m_HashFunctor( key ) & m_nHashBitmask;
+        }
+
+        /// Returns the bucket (ordered list) for \p key
+        template <typename Q>
+        internal_bucket_type& bucket( Q const& key )
+        {
+            return m_Buckets[ hash_value( key ) ];
+        }
+        template <typename Q>
+        internal_bucket_type const& bucket( Q const& key ) const
+        {
+            return m_Buckets[hash_value( key )];
+        }
+        //@endcond
+
+    private:
+        //@cond
+        internal_bucket_type* bucket_begin() const
+        {
+            return m_Buckets;
+        }
+
+        internal_bucket_type* bucket_end() const
+        {
+            return m_Buckets + bucket_count();
+        }
+
+        const_iterator get_const_begin() const
+        {
+            return const_iterator( bucket_begin()->cbegin(), bucket_begin(), bucket_end() );
+        }
+        const_iterator get_const_end() const
+        {
+            return const_iterator(( bucket_end() -1 )->cend(), bucket_end() - 1, bucket_end() );
+        }
+
+        template <typename Stat>
+        typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
+        {
+            new (bucket) internal_bucket_type;
+        }
+
+        template <typename Stat>
+        typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
+        {
+            new (bucket) internal_bucket_type( m_Stat );
+        }
+
+        template <typename List, typename... Args>
+        typename std::enable_if< !is_iterable_list<List>::value, bool>::type
+        bucket_emplace( Args&&... args )
+        {
+            class list_accessor: public List
+            {
+            public:
+                using List::alloc_node;
+                using List::node_to_value;
+                using List::insert_node;
+            };
+
+            auto pNode = list_accessor::alloc_node( std::forward<Args>( args )... );
+            assert( pNode != nullptr );
+            return static_cast<list_accessor&>( bucket( list_accessor::node_to_value( *pNode ))).insert_node( pNode );
+        }
+
+        template <typename List, typename... Args>
+        typename std::enable_if< is_iterable_list<List>::value, bool>::type
+        bucket_emplace( Args&&... args )
+        {
+            class list_accessor: public List
+            {
+            public:
+                using List::alloc_data;
+                using List::insert_node;
+            };
+
+            auto pData = list_accessor::alloc_data( std::forward<Args>( args )... );
+            assert( pData != nullptr );
+            return static_cast<list_accessor&>( bucket( *pData )).insert_node( pData );
+        }
+        //@endcond
     };
 
 }} // namespace cds::container
index b3e7db4..aaa7ee5 100644 (file)
@@ -33,7 +33,6 @@
 
 #include <cds/container/details/michael_set_base.h>
 #include <cds/gc/nogc.h>
-#include <cds/details/allocator.h>
 
 namespace cds { namespace container {
 
@@ -59,23 +58,40 @@ namespace cds { namespace container {
     class MichaelHashSet< cds::gc::nogc, OrderedList, Traits >
     {
     public:
-        typedef cds::gc::nogc gc;        ///< Garbage collector
-        typedef OrderedList bucket_type; ///< type of ordered list to be used as a bucket implementation
-        typedef Traits      traits;      ///< Set traits
+        typedef cds::gc::nogc gc;         ///< Garbage collector
+        typedef OrderedList ordered_list; ///< type of ordered list to be used as a bucket implementation
+        typedef Traits      traits;       ///< Set traits
 
-        typedef typename bucket_type::value_type        value_type;     ///< type of value stored in the list
-        typedef typename bucket_type::key_comparator    key_comparator; ///< key comparison functor
+        typedef typename ordered_list::value_type     value_type;     ///< type of value stored in the list
+        typedef typename ordered_list::key_comparator key_comparator; ///< key comparison functor
+        typedef typename ordered_list::stat           stat;           ///< Internal statistics
 
         /// Hash functor for \ref value_type and all its derivatives that you use
         typedef typename cds::opt::v::hash_selector< typename traits::hash >::type hash;
-        typedef typename traits::item_counter  item_counter; ///< Item counter type
+        typedef typename traits::item_counter item_counter; ///< Item counter type
+        typedef typename traits::allocator    allocator;    ///< Bucket table allocator
+
+        // GC and OrderedList::gc must be the same
+        static_assert(std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
+
+        // atomicity::empty_item_counter is not allowed as a item counter
+        static_assert(!std::is_same<item_counter, atomicity::empty_item_counter>::value,
+            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 
     protected:
         //@cond
-        class internal_bucket_type: public bucket_type
+        typedef typename ordered_list::template select_stat_wrapper< typename ordered_list::stat > bucket_stat;
+
+        typedef typename ordered_list::template rebind_traits<
+            cds::opt::item_counter< cds::atomicity::empty_item_counter >
+            , cds::opt::stat< typename bucket_stat::wrapped_stat >
+        >::type internal_bucket_type_;
+
+        class internal_bucket_type: public internal_bucket_type_
         {
-            typedef bucket_type base_class;
+            typedef internal_bucket_type_ base_class;
         public:
+            using base_class::base_class;
             using base_class::node_type;
             using base_class::alloc_node;
             using base_class::insert_node;
@@ -83,39 +99,19 @@ namespace cds { namespace container {
         };
 
         /// Bucket table allocator
-        typedef cds::details::Allocator< internal_bucket_type, typename traits::allocator >  bucket_table_allocator;
+        typedef typename allocator::template rebind< internal_bucket_type >::other bucket_table_allocator;
 
-        typedef typename bucket_type::iterator        bucket_iterator;
-        typedef typename bucket_type::const_iterator  bucket_const_iterator;
+        typedef typename internal_bucket_type::iterator        bucket_iterator;
+        typedef typename internal_bucket_type::const_iterator  bucket_const_iterator;
         //@endcond
 
     protected:
-        //@cond
-        item_counter    m_ItemCounter;   ///< Item counter
-        hash            m_HashFunctor;   ///< Hash functor
-        internal_bucket_type *   m_Buckets;       ///< bucket table
-        //@endcond
-
-    private:
         //@cond
         const size_t    m_nHashBitmask;
-        //@endcond
-
-    protected:
-        //@cond
-        /// Calculates hash value of \p key
-        template <typename Q>
-        size_t hash_value( const Q& key ) const
-        {
-            return m_HashFunctor( key ) & m_nHashBitmask;
-        }
-
-        /// Returns the bucket (ordered list) for \p key
-        template <typename Q>
-        internal_bucket_type& bucket( const Q& key )
-        {
-            return m_Buckets[ hash_value( key ) ];
-        }
+        item_counter    m_ItemCounter;      ///< Item counter
+        hash            m_HashFunctor;      ///< Hash functor
+        internal_bucket_type*   m_Buckets;  ///< bucket table
+        typename bucket_stat::stat  m_Stat; ///< Internal statistics
         //@endcond
 
     public:
@@ -155,13 +151,13 @@ namespace cds { namespace container {
             };
             \endcode
         */
-        typedef michael_set::details::iterator< bucket_type, false >    iterator;
+        typedef michael_set::details::iterator< internal_bucket_type, false >    iterator;
 
         /// Const forward iterator
         /**
             For iterator's features and requirements see \ref iterator
         */
-        typedef michael_set::details::iterator< bucket_type, true >     const_iterator;
+        typedef michael_set::details::iterator< internal_bucket_type, true >     const_iterator;
 
         /// Returns a forward iterator addressing the first element in a set
         /**
@@ -208,18 +204,6 @@ namespace cds { namespace container {
         }
     //@}
 
-    private:
-        //@cond
-        const_iterator get_const_begin() const
-        {
-            return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
-        }
-        const_iterator get_const_end() const
-        {
-            return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
-        }
-        //@endcond
-
     public:
         /// Initialize hash set
         /**
@@ -234,22 +218,19 @@ namespace cds { namespace container {
             size_t nMaxItemCount,   ///< estimation of max item count in the hash set
             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
         ) : m_nHashBitmask( michael_set::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
+          , m_Buckets( bucket_table_allocator().allocate( bucket_count() ) )
         {
-            // GC and OrderedList::gc must be the same
-            static_assert( std::is_same<gc, typename bucket_type::gc>::value, "GC and OrderedList::gc must be the same");
-
-            // atomicity::empty_item_counter is not allowed as a item counter
-            static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
-                           "cds::atomicity::empty_item_counter is not allowed as a item counter");
-
-            m_Buckets = bucket_table_allocator().NewArray( bucket_count() );
+            for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+                construct_bucket<bucket_stat>( it );
         }
 
         /// Clears hash set and destroys it
         ~MichaelHashSet()
         {
             clear();
-            bucket_table_allocator().Delete( m_Buckets, bucket_count() );
+            for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
+                it->~internal_bucket_type();
+            bucket_table_allocator().deallocate( m_Buckets, bucket_count() );
         }
 
         /// Inserts new node
@@ -405,6 +386,12 @@ namespace cds { namespace container {
             return m_ItemCounter;
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return m_Stat;
+        }
+
         /// Returns the size of hash table
         /**
             Since \p %MichaelHashSet cannot dynamically extend the hash table size,
@@ -415,6 +402,47 @@ namespace cds { namespace container {
         {
             return m_nHashBitmask + 1;
         }
+
+    protected:
+        //@cond
+        /// Calculates hash value of \p key
+        template <typename Q>
+        size_t hash_value( const Q& key ) const
+        {
+            return m_HashFunctor( key ) & m_nHashBitmask;
+        }
+
+        /// Returns the bucket (ordered list) for \p key
+        template <typename Q>
+        internal_bucket_type& bucket( const Q& key )
+        {
+            return m_Buckets[hash_value( key )];
+        }
+        //@endcond
+
+    private:
+        //@cond
+        template <typename Stat>
+        typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
+        {
+            new (bucket) internal_bucket_type;
+        }
+
+        template <typename Stat>
+        typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
+        {
+            new (bucket) internal_bucket_type( m_Stat );
+        }
+
+        const_iterator get_const_begin() const
+        {
+            return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[0]).begin(), m_Buckets, m_Buckets + bucket_count() );
+        }
+        const_iterator get_const_end() const
+        {
+            return const_iterator( const_cast<internal_bucket_type const&>(m_Buckets[bucket_count() - 1]).end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
+        }
+        //@endcond
     };
 
 }} // cds::container
index b264bb1..8cc7fe9 100644 (file)
@@ -50,7 +50,8 @@ namespace cds { namespace intrusive {
 
         Template parameters are:
         - \p GC - Garbage collector used. Note the \p GC must be the same as the GC used for \p OrderedList
-        - \p OrderedList - ordered list implementation used as bucket for hash set, for example, \p MichaelList, \p LazyList, \p IterableList.
+        - \p OrderedList - ordered list implementation used as bucket for hash set, possible implementations:
+            \p MichaelList, \p LazyList, \p IterableList.
             The intrusive ordered list implementation specifies the type \p T stored in the hash-set, the reclamation
             schema \p GC used by hash-set, the comparison functor for the type \p T and other features specific for
             the ordered list.
@@ -364,7 +365,7 @@ namespace cds { namespace intrusive {
 
     public:
         /// Initializes hash set
-        /** @anchor cds_intrusive_MichaelHashSet_hp_ctor
+        /**
             The Michael's hash set is an unbounded container, but its hash table is non-expandable.
             At construction time you should pass estimated maximum item count and a load factor.
             The load factor is average size of one bucket - a small number between 1 and 10.
index a876352..d67504e 100644 (file)
@@ -35,6 +35,8 @@
     <ClCompile Include="..\..\..\test\unit\set\feldman_hashset_rcu_gpt.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\set\feldman_hashset_rcu_shb.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\set\feldman_hashset_rcu_sht.cpp" />\r
+    <ClCompile Include="..\..\..\test\unit\set\michael_iterable_dhp.cpp" />\r
+    <ClCompile Include="..\..\..\test\unit\set\michael_iterable_hp.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\set\michael_lazy_dhp.cpp">\r
       <DisableSpecificWarnings Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">4503</DisableSpecificWarnings>\r
       <DisableSpecificWarnings Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">4503</DisableSpecificWarnings>\r
     <ClInclude Include="..\..\..\test\unit\set\test_feldman_hashset.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_feldman_hashset_hp.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_feldman_hashset_rcu.h" />\r
+    <ClInclude Include="..\..\..\test\unit\set\test_michael_iterable.h" />\r
+    <ClInclude Include="..\..\..\test\unit\set\test_michael_iterable_hp.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_michael_lazy_rcu.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_michael_michael_rcu.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_ordered_set_hp.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_set.h" />\r
+    <ClInclude Include="..\..\..\test\unit\set\test_set_data.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_set_hp.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_set_nogc.h" />\r
     <ClInclude Include="..\..\..\test\unit\set\test_set_rcu.h" />\r
index 80a2f7e..4fe9b8d 100644 (file)
     <ClCompile Include="..\..\..\test\unit\set\feldman_hashset_rcu_sht.cpp">\r
       <Filter>Source Files\FeldmanHashSet</Filter>\r
     </ClCompile>\r
+    <ClCompile Include="..\..\..\test\unit\set\michael_iterable_hp.cpp">\r
+      <Filter>Source Files\MichaelSet</Filter>\r
+    </ClCompile>\r
+    <ClCompile Include="..\..\..\test\unit\set\michael_iterable_dhp.cpp">\r
+      <Filter>Source Files\MichaelSet</Filter>\r
+    </ClCompile>\r
   </ItemGroup>\r
   <ItemGroup>\r
     <ClInclude Include="..\..\..\test\unit\set\test_set.h">\r
     <ClInclude Include="..\..\..\test\unit\set\test_ordered_set_hp.h">\r
       <Filter>Header Files</Filter>\r
     </ClInclude>\r
+    <ClInclude Include="..\..\..\test\unit\set\test_michael_iterable.h">\r
+      <Filter>Header Files</Filter>\r
+    </ClInclude>\r
+    <ClInclude Include="..\..\..\test\unit\set\test_michael_iterable_hp.h">\r
+      <Filter>Header Files</Filter>\r
+    </ClInclude>\r
+    <ClInclude Include="..\..\..\test\unit\set\test_set_data.h">\r
+      <Filter>Header Files</Filter>\r
+    </ClInclude>\r
   </ItemGroup>\r
 </Project>
\ No newline at end of file
index dcd684a..8178121 100644 (file)
@@ -9,6 +9,8 @@ set(CDSGTEST_SET_SOURCES
     feldman_hashset_rcu_gpt.cpp
     feldman_hashset_rcu_shb.cpp
     feldman_hashset_rcu_sht.cpp
+    michael_iterable_hp.cpp
+    michael_iterable_dhp.cpp
     michael_lazy_hp.cpp
     michael_lazy_dhp.cpp
     michael_lazy_nogc.cpp
diff --git a/test/unit/set/michael_iterable_dhp.cpp b/test/unit/set/michael_iterable_dhp.cpp
new file mode 100644 (file)
index 0000000..0ff99a8
--- /dev/null
@@ -0,0 +1,218 @@
+/*
+    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.
+*/
+
+#include "test_michael_iterable_hp.h"
+
+#include <cds/container/iterable_list_dhp.h>
+#include <cds/container/michael_set.h>
+
+namespace {
+    namespace cc = cds::container;
+    typedef cds::gc::DHP gc_type;
+
+    class MichaelIterableSet_DHP : public cds_test::michael_iterable_set_hp
+    {
+    protected:
+        typedef cds_test::michael_iterable_set_hp base_class;
+
+        void SetUp()
+        {
+            typedef cc::IterableList< gc_type, int_item > list_type;
+            typedef cc::MichaelHashSet< gc_type, list_type >   set_type;
+
+            cds::gc::dhp::GarbageCollector::Construct( 16, set_type::c_nHazardPtrCount );
+            cds::threading::Manager::attachThread();
+        }
+
+        void TearDown()
+        {
+            cds::threading::Manager::detachThread();
+            cds::gc::dhp::GarbageCollector::Destruct();
+        }
+    };
+
+    TEST_F( MichaelIterableSet_DHP, compare )
+    {
+        typedef cc::IterableList< gc_type, int_item,
+            typename cc::iterable_list::make_traits<
+                cds::opt::compare< cmp >
+            >::type
+        > list_type;
+
+        typedef cc::MichaelHashSet< gc_type, list_type, 
+            typename cc::michael_set::make_traits<
+                cds::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_DHP, less )
+    {
+        typedef cc::IterableList< gc_type, int_item,
+            typename cc::iterable_list::make_traits<
+                cds::opt::less< base_class::less >
+            >::type
+        > list_type;
+
+        typedef cc::MichaelHashSet< gc_type, list_type, 
+            typename cc::michael_set::make_traits<
+                cds::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_DHP, cmpmix )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cmp compare;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        typedef cc::MichaelHashSet< gc_type, list_type, 
+            typename cc::michael_set::make_traits<
+                cds::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_DHP, item_counting )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef cmp compare;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 3 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_DHP, backoff )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef cmp compare;
+            typedef cds::backoff::exponential<cds::backoff::pause, cds::backoff::yield> back_off;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits : public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_DHP, seq_cst )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cds::opt::v::sequential_consistent memory_model;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits : public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_DHP, stat )
+    {
+        struct list_traits: public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::iterable_list::stat<> stat;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_DHP, wrapped_stat )
+    {
+        struct list_traits: public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::iterable_list::wrapped_stat<> stat;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+} // namespace
diff --git a/test/unit/set/michael_iterable_hp.cpp b/test/unit/set/michael_iterable_hp.cpp
new file mode 100644 (file)
index 0000000..b3313e7
--- /dev/null
@@ -0,0 +1,219 @@
+/*
+    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.
+*/
+
+#include "test_michael_iterable_hp.h"
+
+#include <cds/container/iterable_list_hp.h>
+#include <cds/container/michael_set.h>
+
+namespace {
+    namespace cc = cds::container;
+    typedef cds::gc::HP gc_type;
+
+    class MichaelIterableSet_HP : public cds_test::michael_iterable_set_hp
+    {
+    protected:
+        typedef cds_test::michael_iterable_set_hp base_class;
+
+        void SetUp()
+        {
+            typedef cc::IterableList< gc_type, int_item > list_type;
+            typedef cc::MichaelHashSet< gc_type, list_type >   set_type;
+
+            // +3 - for guarded_ptr, iterators
+            cds::gc::hp::GarbageCollector::Construct( set_type::c_nHazardPtrCount + 3, 1, 16 );
+            cds::threading::Manager::attachThread();
+        }
+
+        void TearDown()
+        {
+            cds::threading::Manager::detachThread();
+            cds::gc::hp::GarbageCollector::Destruct( true );
+        }
+    };
+
+    TEST_F( MichaelIterableSet_HP, compare )
+    {
+        typedef cc::IterableList< gc_type, int_item,
+            typename cc::iterable_list::make_traits<
+                cds::opt::compare< cmp >
+            >::type
+        > list_type;
+
+        typedef cc::MichaelHashSet< gc_type, list_type, 
+            typename cc::michael_set::make_traits<
+                cds::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_HP, less )
+    {
+        typedef cc::IterableList< gc_type, int_item,
+            typename cc::iterable_list::make_traits<
+                cds::opt::less< base_class::less >
+            >::type
+        > list_type;
+
+        typedef cc::MichaelHashSet< gc_type, list_type, 
+            typename cc::michael_set::make_traits<
+                cds::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_HP, cmpmix )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cmp compare;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        typedef cc::MichaelHashSet< gc_type, list_type, 
+            typename cc::michael_set::make_traits<
+                cds::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_HP, item_counting )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef cmp compare;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 3 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_HP, backoff )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef cmp compare;
+            typedef cds::backoff::exponential<cds::backoff::pause, cds::backoff::yield> back_off;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits : public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_HP, seq_cst )
+    {
+        struct list_traits : public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cds::opt::v::sequential_consistent memory_model;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits : public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_HP, stat )
+    {
+        struct list_traits: public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::iterable_list::stat<> stat;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelIterableSet_HP, wrapped_stat )
+    {
+        struct list_traits: public cc::iterable_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::iterable_list::wrapped_stat<> stat;
+        };
+        typedef cc::IterableList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+} // namespace
index 1ec2a93..be57e99 100644 (file)
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_hp.h"
@@ -194,4 +194,46 @@ namespace {
         test( s );
     }
 
+    TEST_F( MichaelLazySet_DHP, stat )
+    {
+        struct list_traits: public cc::lazy_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::lazy_list::stat<> stat;
+        };
+        typedef cc::LazyList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelLazySet_DHP, wrapped_stat )
+    {
+        struct list_traits: public cc::lazy_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::lazy_list::wrapped_stat<> stat;
+        };
+        typedef cc::LazyList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index af16339..8e3cee2 100644 (file)
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_hp.h"
@@ -195,4 +195,46 @@ namespace {
         test( s );
     }
 
+    TEST_F( MichaelLazySet_HP, stat )
+    {
+        struct list_traits: public cc::lazy_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::lazy_list::stat<> stat;
+        };
+        typedef cc::LazyList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelLazySet_HP, wrapped_stat )
+    {
+        struct list_traits: public cc::lazy_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::lazy_list::wrapped_stat<> stat;
+        };
+        typedef cc::LazyList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index 0a7751c..76b9cb1 100644 (file)
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_nogc.h"
@@ -185,4 +185,46 @@ namespace {
         test( s );
     }
 
+    TEST_F( MichaelLazySet_NoGC, stat )
+    {
+        struct list_traits: public cc::lazy_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::lazy_list::stat<> stat;
+        };
+        typedef cc::LazyList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelLazySet_NoGC, wrapped_stat )
+    {
+        struct list_traits: public cc::lazy_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::lazy_list::wrapped_stat<> stat;
+        };
+        typedef cc::LazyList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index 73f8b1f..046e0c2 100644 (file)
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_hp.h"
@@ -173,4 +173,46 @@ namespace {
         test( s );
     }
 
+    TEST_F( MichaelSet_DHP, stat )
+    {
+        struct list_traits: public cc::michael_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::michael_list::stat<> stat;
+        };
+        typedef cc::MichaelList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelSet_DHP, wrapped_stat )
+    {
+        struct list_traits: public cc::michael_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::michael_list::wrapped_stat<> stat;
+        };
+        typedef cc::MichaelList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index 29107d4..dc85ec7 100644 (file)
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_hp.h"
@@ -174,4 +174,46 @@ namespace {
         test( s );
     }
 
+    TEST_F( MichaelSet_HP, stat )
+    {
+        struct list_traits: public cc::michael_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::michael_list::stat<> stat;
+        };
+        typedef cc::MichaelList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelSet_HP, wrapped_stat )
+    {
+        struct list_traits: public cc::michael_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::michael_list::wrapped_stat<> stat;
+        };
+        typedef cc::MichaelList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits > set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
index 0f493ff..5dda78b 100644 (file)
@@ -25,7 +25,7 @@
     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.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "test_set_nogc.h"
@@ -164,4 +164,46 @@ namespace {
         test( s );
     }
 
+    TEST_F( MichaelSet_NoGC, stat )
+    {
+        struct list_traits: public cc::michael_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::michael_list::stat<> stat;
+        };
+        typedef cc::MichaelList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
+    TEST_F( MichaelSet_NoGC, wrapped_stat )
+    {
+        struct list_traits: public cc::michael_list::traits
+        {
+            typedef base_class::less less;
+            typedef cds::backoff::pause back_off;
+            typedef cc::michael_list::wrapped_stat<> stat;
+        };
+        typedef cc::MichaelList< gc_type, int_item, list_traits > list_type;
+
+        struct set_traits: public cc::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef cds::atomicity::item_counter item_counter;
+        };
+        typedef cc::MichaelHashSet< gc_type, list_type, set_traits >set_type;
+
+        set_type s( kSize, 4 );
+        test( s );
+    }
+
 } // namespace
diff --git a/test/unit/set/test_michael_iterable.h b/test/unit/set/test_michael_iterable.h
new file mode 100644 (file)
index 0000000..9742a1c
--- /dev/null
@@ -0,0 +1,379 @@
+/*
+    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 CDSUNIT_SET_TEST_MICHAEL_ITERABLE_H
+#define CDSUNIT_SET_TEST_MICHAEL_ITERABLE_H
+
+#include "test_set_data.h"
+
+namespace cds_test {
+
+    class michael_iterable_set: public container_set_data
+    {
+    protected:
+        template <typename Set>
+        void test( Set& s )
+        {
+            // Precondition: set is empty
+            // Postcondition: set is empty
+
+            EXPECT_TRUE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, 0 );
+            size_t const nSetSize = kSize;
+
+            typedef typename Set::value_type value_type;
+
+            std::vector< value_type > data;
+            std::vector< size_t> indices;
+            data.reserve( kSize );
+            indices.reserve( kSize );
+            for ( size_t key = 0; key < kSize; ++key ) {
+                data.push_back( value_type( static_cast<int>(key) ) );
+                indices.push_back( key );
+            }
+            shuffle( indices.begin(), indices.end() );
+
+            // insert/find
+            for ( auto idx : indices ) {
+                auto& i = data[idx];
+
+                EXPECT_FALSE( s.contains( i.nKey ) );
+                EXPECT_FALSE( s.contains( i ) );
+                EXPECT_FALSE( s.contains( other_item( i.key() ), other_less()));
+                EXPECT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
+                EXPECT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
+                EXPECT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
+                EXPECT_TRUE( s.find( i ) == s.end());
+                EXPECT_TRUE( s.find( i.nKey ) == s.end() );
+                EXPECT_TRUE( s.find_with( other_item( i.key()), other_less()) == s.end() );
+
+                std::pair<bool, bool> updResult;
+
+                std::string str;
+                updResult = s.update( i.key(), []( value_type&, value_type* old )
+                {
+                    EXPECT_TRUE( old == nullptr );
+                }, false );
+                EXPECT_FALSE( updResult.first );
+                EXPECT_FALSE( updResult.second );
+
+                switch ( idx % 11 ) {
+                case 0:
+                    EXPECT_TRUE( s.insert( i ));
+                    EXPECT_FALSE( s.insert( i ));
+                    updResult = s.update( i, []( value_type& val, value_type* old) 
+                        {
+                            ASSERT_FALSE( old == nullptr );
+                            EXPECT_EQ( val.key(), old->key() );
+                        }, false );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+                    break;
+                case 1:
+                    EXPECT_TRUE( s.insert( i.key() ));
+                    EXPECT_FALSE( s.insert( i.key() ));
+                    updResult = s.update( i.key(), []( value_type& val, value_type* old) 
+                        {
+                            ASSERT_FALSE( old == nullptr );
+                            EXPECT_EQ( val.key(), old->key() );
+                        }, false );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+                    break;
+                case 2:
+                    EXPECT_TRUE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
+                    EXPECT_FALSE( s.insert( i, []( value_type& v ) { ++v.nFindCount; } ));
+                    EXPECT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) 
+                        {
+                            EXPECT_EQ( v.key(), key );
+                            EXPECT_EQ( v.nFindCount, 1 );
+                        }));
+                    break;
+                case 3:
+                    EXPECT_TRUE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
+                    EXPECT_FALSE( s.insert( i.key(), []( value_type& v ) { ++v.nFindCount; } ));
+                    EXPECT_TRUE( s.find( i.nKey, []( value_type const& v, int key ) 
+                        {
+                            EXPECT_EQ( v.key(), key );
+                            EXPECT_EQ( v.nFindCount, 1 );
+                        }));
+                    break;
+                case 4:
+                    updResult = s.update( i, [&i]( value_type& v, value_type* old )
+                        {
+                            EXPECT_TRUE( old == nullptr );
+                            EXPECT_EQ( v.key(), i.key() );
+                            ++v.nUpdateNewCount;
+                        });
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_TRUE( updResult.second );
+
+                    updResult = s.update( i, []( value_type& v, value_type* old )
+                        {
+                            ASSERT_FALSE( old == nullptr );
+                            EXPECT_EQ( v.key(), old->key() );
+                            EXPECT_EQ( old->nUpdateNewCount, 1 );
+                            v.nUpdateNewCount = old->nUpdateNewCount;
+                            ++v.nUpdateCount;
+                        }, false );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+
+                    EXPECT_TRUE( s.find( i.nKey, []( value_type const& v, int key )
+                        {
+                            EXPECT_EQ( v.key(), key );
+                            EXPECT_EQ( v.nUpdateNewCount, 1 );
+                            EXPECT_EQ( v.nUpdateCount, 1 );
+                    }));
+                    break;
+                case 5:
+                    updResult = s.update( i.key(), [&i]( value_type& v, value_type* old )
+                        {
+                            EXPECT_TRUE( old == nullptr );
+                            EXPECT_EQ( v.key(), i.key() );
+                            ++v.nUpdateNewCount;
+                        });
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_TRUE( updResult.second );
+
+                    updResult = s.update( i.key(), []( value_type& v, value_type* old )
+                        {
+                            EXPECT_FALSE( old == nullptr );
+                            EXPECT_EQ( v.key(), old->key() );
+                            EXPECT_EQ( old->nUpdateNewCount, 1 );
+                            v.nUpdateNewCount = old->nUpdateNewCount;
+                            ++v.nUpdateCount;
+                        }, false );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+
+                    EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
+                        {
+                            EXPECT_EQ( v.key(), arg.key() );
+                            EXPECT_EQ( v.nUpdateNewCount, 1 );
+                            EXPECT_EQ( v.nUpdateCount, 1 );
+                    }));
+                    break;
+                case 6:
+                    EXPECT_TRUE( s.emplace( i.key()));
+                    EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
+                        {
+                            EXPECT_EQ( v.key(), arg.key() );
+                            EXPECT_EQ( v.nVal, arg.nVal );
+                        }));
+                    break;
+                case 7:
+                    str = "Hello!";
+                    EXPECT_TRUE( s.emplace( i.key(), std::move( str )));
+                    EXPECT_TRUE( str.empty());
+                    EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
+                        {
+                            EXPECT_EQ( v.key(), arg.key() );
+                            EXPECT_EQ( v.nVal, arg.nVal );
+                            EXPECT_EQ( v.strVal, std::string( "Hello!" ));
+                        } ));
+                    break;
+                case 8:
+                    str = "Hello!";
+                    EXPECT_TRUE( s.insert( value_type( i.key(), std::move( str ))) );
+                    EXPECT_TRUE( str.empty() );
+                    EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
+                    {
+                        EXPECT_EQ( v.key(), arg.key() );
+                        EXPECT_EQ( v.nVal, arg.nVal );
+                        EXPECT_EQ( v.strVal, std::string( "Hello!" ) );
+                    } ) );
+                    break;
+                case 9:
+                    updResult = s.upsert( i.key(), false );
+                    EXPECT_FALSE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+
+                    updResult = s.upsert( i.key());
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_TRUE( updResult.second );
+
+                    updResult = s.upsert( i.key(), false );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+
+                    EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
+                    {
+                        EXPECT_EQ( v.key(), arg.key() );
+                    } ) );
+                    break;
+                case 10:
+                    updResult = s.upsert( i, false );
+                    EXPECT_FALSE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+
+                    updResult = s.upsert( i );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_TRUE( updResult.second );
+
+                    updResult = s.upsert( i, false );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+
+                    EXPECT_TRUE( s.find( i, []( value_type const& v, value_type const& arg )
+                    {
+                        EXPECT_EQ( v.key(), arg.key() );
+                    } ) );
+                    break;
+                default:
+                    // forgot anything?..
+                    EXPECT_TRUE( false );
+                }
+
+                EXPECT_TRUE( s.contains( i.nKey ) );
+                EXPECT_TRUE( s.contains( i ) );
+                EXPECT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
+                EXPECT_TRUE( s.find( i.nKey, []( value_type&, int ) {} ) );
+                EXPECT_TRUE( s.find( i, []( value_type&, value_type const& ) {} ) );
+                EXPECT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type&, other_item const& ) {} ) );
+                EXPECT_FALSE( s.find( i.nKey ) == s.end());
+                EXPECT_FALSE( s.find( i ) == s.end() );
+                EXPECT_FALSE( s.find_with( other_item( i.key() ), other_less()) == s.end() );
+            }
+
+            EXPECT_FALSE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, nSetSize );
+
+            // erase
+            shuffle( indices.begin(), indices.end() );
+            for ( auto idx : indices ) {
+                auto& i = data[idx];
+
+                EXPECT_TRUE( s.contains( i.nKey ) );
+                EXPECT_TRUE( s.contains( i ) );
+                EXPECT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
+                EXPECT_TRUE( s.find( i.nKey, []( value_type& v, int ) 
+                    { 
+                        v.nFindCount = 1;
+                    }));
+                EXPECT_TRUE( s.find( i, []( value_type& v, value_type const& ) 
+                    { 
+                        EXPECT_EQ( ++v.nFindCount, 2 );
+                    }));
+                EXPECT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) 
+                    { 
+                        EXPECT_EQ( ++v.nFindCount, 3 );
+                    }));
+
+                int nKey = i.key() - 1;
+                switch ( idx % 6 ) {
+                case 0:
+                    EXPECT_TRUE( s.erase( i.key()));
+                    EXPECT_FALSE( s.erase( i.key()));
+                    break;
+                case 1:
+                    EXPECT_TRUE( s.erase( i ));
+                    EXPECT_FALSE( s.erase( i ));
+                    break;
+                case 2:
+                    EXPECT_TRUE( s.erase_with( other_item( i.key()), other_less()));
+                    EXPECT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
+                    break;
+                case 3:
+                    EXPECT_TRUE( s.erase( i.key(), [&nKey]( value_type const& v )
+                        {
+                            nKey = v.key();
+                        } ));
+                    EXPECT_EQ( i.key(), nKey );
+
+                    nKey = i.key() - 1;
+                    EXPECT_FALSE( s.erase( i.key(), [&nKey]( value_type const& v )
+                        {
+                            nKey = v.key();
+                        } ));
+                    EXPECT_EQ( i.key(), nKey + 1 );
+                    break;
+                case 4:
+                    EXPECT_TRUE( s.erase( i, [&nKey]( value_type const& v )
+                        {
+                            nKey = v.key();
+                        } ));
+                    EXPECT_EQ( i.key(), nKey );
+
+                    nKey = i.key() - 1;
+                    EXPECT_FALSE( s.erase( i, [&nKey]( value_type const& v )
+                        {
+                            nKey = v.key();
+                        } ));
+                    EXPECT_EQ( i.key(), nKey + 1 );
+                    break;
+                case 5:
+                    EXPECT_TRUE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
+                        {
+                            nKey = v.key();
+                        } ));
+                    EXPECT_EQ( i.key(), nKey );
+
+                    nKey = i.key() - 1;
+                    EXPECT_FALSE( s.erase_with( other_item( i.key()), other_less(), [&nKey]( value_type const& v )
+                        {
+                            nKey = v.key();
+                        } ));
+                    EXPECT_EQ( i.key(), nKey + 1 );
+                    break;
+                }
+
+                EXPECT_FALSE( s.contains( i.nKey ) );
+                EXPECT_FALSE( s.contains( i ) );
+                EXPECT_FALSE( s.contains( other_item( i.key() ), other_less()));
+                EXPECT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
+                EXPECT_FALSE( s.find( i, []( value_type&, value_type const& ) {} ));
+                EXPECT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
+            }
+            EXPECT_TRUE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, 0 );
+
+
+            // clear
+            for ( auto& i : data ) {
+                EXPECT_TRUE( s.insert( i ) );
+            }
+
+            EXPECT_FALSE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, nSetSize );
+
+            s.clear();
+
+            EXPECT_TRUE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, 0 );
+
+            EXPECT_TRUE( s.begin() == s.end() );
+            EXPECT_TRUE( s.cbegin() == s.cend() );
+        }
+    };
+
+} // namespace cds_test
+
+#endif // CDSUNIT_SET_TEST_MICHAEL_ITERABLE_H
diff --git a/test/unit/set/test_michael_iterable_hp.h b/test/unit/set/test_michael_iterable_hp.h
new file mode 100644 (file)
index 0000000..1a86767
--- /dev/null
@@ -0,0 +1,153 @@
+/*
+    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 CDSUNIT_SET_TEST_SET_HP_H
+#define CDSUNIT_SET_TEST_SET_HP_H
+
+#include "test_michael_iterable.h"
+
+namespace cds_test {
+
+    class michael_iterable_set_hp: public michael_iterable_set
+    {
+        typedef michael_iterable_set base_class;
+
+    protected:
+        template <typename Set>
+        void test( Set& s )
+        {
+            // Precondition: set is empty
+            // Postcondition: set is empty
+
+            EXPECT_TRUE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, 0 );
+
+            base_class::test( s );
+
+            typedef typename Set::value_type value_type;
+
+            size_t const nSetSize = kSize;
+            std::vector< value_type > data;
+            std::vector< size_t> indices;
+            data.reserve( kSize );
+            indices.reserve( kSize );
+            for ( size_t key = 0; key < kSize; ++key ) {
+                data.push_back( value_type( static_cast<int>(key) ) );
+                indices.push_back( key );
+            }
+            shuffle( indices.begin(), indices.end() );
+
+            for ( auto& i : data ) {
+                EXPECT_TRUE( s.insert( i ) );
+            }
+            EXPECT_FALSE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, nSetSize );
+
+            // iterator test
+            for ( auto it = s.begin(); it != s.end(); ++it ) {
+                it->nFindCount = it->key() * 3;
+            }
+
+            for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
+                EXPECT_EQ( it->nFindCount, it->key() * 3 );
+            }
+
+            typedef typename Set::guarded_ptr guarded_ptr;
+            guarded_ptr gp;
+
+            // get()
+            for ( auto idx : indices ) {
+                auto& i = data[idx];
+
+                EXPECT_TRUE( !gp );
+                switch ( idx % 3 ) {
+                case 0:
+                    gp = s.get( i.key() );
+                    ASSERT_FALSE( !gp );
+                    break;
+                case 1:
+                    gp = s.get( i );
+                    ASSERT_FALSE( !gp );
+                    break;
+                case 2:
+                    gp = s.get_with( other_item( i.key() ), other_less() );
+                    ASSERT_FALSE( !gp );
+                }
+                EXPECT_EQ( gp->key(), i.key() );
+                EXPECT_EQ( gp->nFindCount, i.key() * 3 );
+                gp->nFindCount *= 2;
+
+                gp.release();
+            }
+
+            // extract()
+            for ( auto idx : indices ) {
+                auto& i = data[idx];
+
+                EXPECT_TRUE( !gp );
+                switch ( idx % 3 ) {
+                case 0:
+                    gp = s.extract( i.key() );
+                    ASSERT_FALSE( !gp );
+                    break;
+                case 1:
+                    gp = s.extract( i );
+                    ASSERT_FALSE( !gp );
+                    break;
+                case 2:
+                    gp = s.extract_with( other_item( i.key() ), other_less() );
+                    ASSERT_FALSE( !gp );
+                    break;
+                }
+                EXPECT_EQ( gp->key(), i.key() );
+                EXPECT_EQ( gp->nFindCount, i.key() * 6 );
+
+                switch ( idx % 3 ) {
+                case 0:
+                    gp = s.extract( i.key() );
+                    break;
+                case 1:
+                    gp = s.extract( i );
+                    break;
+                case 2:
+                    gp = s.extract_with( other_item( i.key() ), other_less() );
+                    break;
+                }
+                EXPECT_TRUE( !gp );
+            }
+
+            EXPECT_TRUE( s.empty() );
+            EXPECT_CONTAINER_SIZE( s, 0 );
+        }
+
+    };
+} // namespace cds_test
+
+#endif // CDSUNIT_SET_TEST_SET_HP_H
index d3a7a90..fd3957a 100644 (file)
 #ifndef CDSUNIT_SET_TEST_SET_H
 #define CDSUNIT_SET_TEST_SET_H
 
-#include <cds_test/check_size.h>
-#include <cds_test/fixture.h>
+#include "test_set_data.h"
 
 #include <cds/opt/hash.h>
-#include <functional>   // ref
-
-// forward declaration
-namespace cds { namespace container {}}
 
 namespace cds_test {
-    namespace co = cds::opt;
 
-    class container_set : public fixture
+    class container_set : public container_set_data
     {
-    public:
-        static size_t const kSize = 1000;
-
-        struct stat
-        {
-            unsigned int nFindCount;
-            unsigned int nUpdateNewCount;
-            unsigned int nUpdateCount;
-            mutable unsigned int nEraseCount;
-
-            stat()
-            {
-                clear_stat();
-            }
-
-            void clear_stat()
-            {
-                memset( this, 0, sizeof( *this ) );
-            }
-        };
-
-        struct other_item {
-            int nKey;
-
-            explicit other_item( int k )
-                : nKey( k )
-            {}
-
-            int key() const
-            {
-                return nKey;
-            }
-        };
-
-        struct int_item: public stat
-        {
-            int nKey;
-            int nVal;
-            std::string strVal;
-
-            int_item()
-                : nKey( 0 )
-                , nVal( 0 )
-            {}
-
-            explicit int_item( int k )
-                : nKey( k )
-                , nVal( k * 2 )
-            {}
-
-            template <typename Q>
-            explicit int_item( Q const& src )
-                : nKey( src.key() )
-                , nVal( 0 )
-            {}
-
-            int_item( int_item const& src )
-                : nKey( src.nKey )
-                , nVal( src.nVal )
-                , strVal( src.strVal )
-            {}
-
-            int_item( int_item&& src )
-                : nKey( src.nKey )
-                , nVal( src.nVal )
-                , strVal( std::move( src.strVal ) )
-            {}
-
-            int_item( int k, std::string&& s )
-                : nKey( k )
-                , nVal( k * 2 )
-                , strVal( std::move( s ) )
-            {}
-
-            explicit int_item( other_item const& s )
-                : nKey( s.key() )
-                , nVal( s.key() * 2 )
-            {}
-
-            int key() const
-            {
-                return nKey;
-            }
-        };
-
-        struct hash_int {
-            size_t operator()( int i ) const
-            {
-                return co::v::hash<int>()(i);
-            }
-            template <typename Item>
-            size_t operator()( const Item& i ) const
-            {
-                return (*this)(i.key());
-            }
-        };
-
-        struct simple_item_counter {
-            size_t  m_nCount;
-
-            simple_item_counter()
-                : m_nCount( 0 )
-            {}
-
-            size_t operator ++()
-            {
-                return ++m_nCount;
-            }
-
-            size_t operator --()
-            {
-                return --m_nCount;
-            }
-
-            void reset()
-            {
-                m_nCount = 0;
-            }
-
-            operator size_t() const
-            {
-                return m_nCount;
-            }
-
-        };
-
-        struct less
-        {
-            bool operator ()( int_item const& v1, int_item const& v2 ) const
-            {
-                return v1.key() < v2.key();
-            }
-
-            template <typename Q>
-            bool operator ()( int_item const& v1, const Q& v2 ) const
-            {
-                return v1.key() < v2;
-            }
-
-            template <typename Q>
-            bool operator ()( const Q& v1, int_item const& v2 ) const
-            {
-                return v1 < v2.key();
-            }
-        };
-
-        struct cmp {
-            int operator ()( int_item const& v1, int_item const& v2 ) const
-            {
-                if ( v1.key() < v2.key() )
-                    return -1;
-                return v1.key() > v2.key() ? 1 : 0;
-            }
-
-            template <typename T>
-            int operator ()( T const& v1, int v2 ) const
-            {
-                if ( v1.key() < v2 )
-                    return -1;
-                return v1.key() > v2 ? 1 : 0;
-            }
-
-            template <typename T>
-            int operator ()( int v1, T const& v2 ) const
-            {
-                if ( v1 < v2.key() )
-                    return -1;
-                return v1 > v2.key() ? 1 : 0;
-            }
-        };
-
-        struct other_less {
-            template <typename Q, typename T>
-            bool operator()( Q const& lhs, T const& rhs ) const
-            {
-                return lhs.key() < rhs.key();
-            }
-        };
-
     protected:
         template <typename Set>
         void test( Set& s )
diff --git a/test/unit/set/test_set_data.h b/test/unit/set/test_set_data.h
new file mode 100644 (file)
index 0000000..2242fdf
--- /dev/null
@@ -0,0 +1,229 @@
+/*
+    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 CDSUNIT_SET_TEST_SET_DATA_H
+#define CDSUNIT_SET_TEST_SET_DATA_H
+
+#include <cds_test/check_size.h>
+#include <cds_test/fixture.h>
+
+#include <cds/opt/hash.h>
+
+// forward declaration
+namespace cds { namespace container {}}
+
+namespace cds_test {
+    namespace co = cds::opt;
+
+    class container_set_data : public fixture
+    {
+    public:
+        static size_t const kSize = 1000;
+
+        struct stat
+        {
+            unsigned int nFindCount;
+            unsigned int nUpdateNewCount;
+            unsigned int nUpdateCount;
+            mutable unsigned int nEraseCount;
+
+            stat()
+            {
+                clear_stat();
+            }
+
+            void clear_stat()
+            {
+                memset( this, 0, sizeof( *this ) );
+            }
+        };
+
+        struct other_item {
+            int nKey;
+
+            explicit other_item( int k )
+                : nKey( k )
+            {}
+
+            int key() const
+            {
+                return nKey;
+            }
+        };
+
+        struct int_item: public stat
+        {
+            int nKey;
+            int nVal;
+            std::string strVal;
+
+            int_item()
+                : nKey( 0 )
+                , nVal( 0 )
+            {}
+
+            explicit int_item( int k )
+                : nKey( k )
+                , nVal( k * 2 )
+            {}
+
+            template <typename Q>
+            explicit int_item( Q const& src )
+                : nKey( src.key() )
+                , nVal( 0 )
+            {}
+
+            int_item( int_item const& src )
+                : nKey( src.nKey )
+                , nVal( src.nVal )
+                , strVal( src.strVal )
+            {}
+
+            int_item( int_item&& src )
+                : nKey( src.nKey )
+                , nVal( src.nVal )
+                , strVal( std::move( src.strVal ) )
+            {}
+
+            int_item( int k, std::string&& s )
+                : nKey( k )
+                , nVal( k * 2 )
+                , strVal( std::move( s ) )
+            {}
+
+            explicit int_item( other_item const& s )
+                : nKey( s.key() )
+                , nVal( s.key() * 2 )
+            {}
+
+            int key() const
+            {
+                return nKey;
+            }
+        };
+
+        struct hash_int {
+            size_t operator()( int i ) const
+            {
+                return co::v::hash<int>()(i);
+            }
+            template <typename Item>
+            size_t operator()( const Item& i ) const
+            {
+                return (*this)(i.key());
+            }
+        };
+
+        struct simple_item_counter {
+            size_t  m_nCount;
+
+            simple_item_counter()
+                : m_nCount( 0 )
+            {}
+
+            size_t operator ++()
+            {
+                return ++m_nCount;
+            }
+
+            size_t operator --()
+            {
+                return --m_nCount;
+            }
+
+            void reset()
+            {
+                m_nCount = 0;
+            }
+
+            operator size_t() const
+            {
+                return m_nCount;
+            }
+
+        };
+
+        struct less
+        {
+            bool operator ()( int_item const& v1, int_item const& v2 ) const
+            {
+                return v1.key() < v2.key();
+            }
+
+            template <typename Q>
+            bool operator ()( int_item const& v1, const Q& v2 ) const
+            {
+                return v1.key() < v2;
+            }
+
+            template <typename Q>
+            bool operator ()( const Q& v1, int_item const& v2 ) const
+            {
+                return v1 < v2.key();
+            }
+        };
+
+        struct cmp {
+            int operator ()( int_item const& v1, int_item const& v2 ) const
+            {
+                if ( v1.key() < v2.key() )
+                    return -1;
+                return v1.key() > v2.key() ? 1 : 0;
+            }
+
+            template <typename T>
+            int operator ()( T const& v1, int v2 ) const
+            {
+                if ( v1.key() < v2 )
+                    return -1;
+                return v1.key() > v2 ? 1 : 0;
+            }
+
+            template <typename T>
+            int operator ()( int v1, T const& v2 ) const
+            {
+                if ( v1 < v2.key() )
+                    return -1;
+                return v1 > v2.key() ? 1 : 0;
+            }
+        };
+
+        struct other_less {
+            template <typename Q, typename T>
+            bool operator()( Q const& lhs, T const& rhs ) const
+            {
+                return lhs.key() < rhs.key();
+            }
+        };
+    };
+
+} // namespace cds_test
+
+#endif // CDSUNIT_SET_TEST_SET_DATA_H