intrusive MultiLevelHashSet:

- added iterator test
- fixed iterator bugs

diff --git a/cds/intrusive/impl/multilevel_hashset.h b/cds/intrusive/impl/multilevel_hashset.h
index 860a7cd25acf3cbffae952e104eda31e595df209..42ffefd6a21c06c6605510627af89081fdb8ad1e 100644 (file)
--- a/cds/intrusive/impl/multilevel_hashset.h
+++ b/cds/intrusive/impl/multilevel_hashset.h
@@ -102,6 +102,7 @@ namespace cds { namespace intrusive {
                 decltype( hash_accessor()( std::declval<T>()) )
             >::type
         >::type hash_type;
+        //typedef typename std::result_of< hash_accessor( std::declval<T>()) >::type hash_type;
         static_assert( !std::is_pointer<hash_type>::value, "hash_accessor should return a reference to hash value" );
 
         typedef typename traits::disposer disposer; ///< data node disposer
@@ -172,7 +173,7 @@ namespace cds { namespace intrusive {
         template <bool IsConst>
         class bidirectional_iterator
         {
-            friend class MultLevelHashSet;
+            friend class MultiLevelHashSet;
 
             array_node *        m_pNode;    ///< current array node
             size_t              m_idx;      ///< current position in m_pNode
@@ -236,16 +237,16 @@ namespace cds { namespace intrusive {
                 m_guard.clear();
             }
 
-            template <bool IsConst1, bool IsConst2>
-            friend bool operator ==(bidirectional_iterator<IsConst1> const& lhs, bidirectional_iterator<IsConst2> const& rhs)
+            template <bool IsConst2>
+            bool operator ==(bidirectional_iterator<IsConst2> const& rhs) const
             {
-                return lhs.m_pNode == rhs.m_pNode && lhs.m_idx == rhs.m_idx && lhs.m_set == rhs.m_set;
+                return m_pNode == rhs.m_pNode && m_idx == rhs.m_idx && m_set == rhs.m_set;
             }
 
-            template <bool IsConst1, bool IsConst2>
-            friend bool operator !=(bidirectional_iterator<IsConst1> const& lhs, bidirectional_iterator<IsConst2> const& rhs)
+            template <bool IsConst2>
+            bool operator !=(bidirectional_iterator<IsConst2> const& rhs) const
             {
-                return !( lhs == rhs );
+                return !( *this == rhs );
             }
 
         protected:
@@ -265,7 +266,7 @@ namespace cds { namespace intrusive {
 
             value_ptr pointer() const CDS_NOEXCEPT
             {
-                return m_guard.template get<value_ptr>();
+                return m_guard.template get<value_type>();
             }
 
             void forward()
@@ -293,19 +294,22 @@ namespace cds { namespace intrusive {
                             // the slot is converting to array node right now - skip the node
                             ++idx;
                         }
-                        else if ( slot.ptr() ) {
-                            // data node
-                            if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
-                                m_pNode = pNode;
-                                m_idx = idx;
-                                return;
+                        else {
+                            if ( slot.ptr()) {
+                                // data node
+                                if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
+                                    m_pNode = pNode;
+                                    m_idx = idx;
+                                    return;
+                                }
                             }
+                            ++idx;
                         }
                     }
                     else {
                         // up to parent node
                         if ( pNode->pParent ) {
-                            idx = pNode->m_idx + 1;
+                            idx = pNode->idxParent + 1;
                             pNode = pNode->pParent;
                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
                         }
@@ -348,19 +352,22 @@ namespace cds { namespace intrusive {
                             // the slot is converting to array node right now - skip the node
                             --idx;
                         }
-                        else if ( slot.ptr() ) {
-                            // data node
-                            if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
-                                m_pNode = pNode;
-                                m_idx = idx;
-                                return;
+                        else {
+                            if ( slot.ptr()) {
+                                // data node
+                                if ( m_guard.protect( pNode->nodes[idx], [](node_ptr p) -> value_type * { return p.ptr(); }) == slot ) {
+                                    m_pNode = pNode;
+                                    m_idx = idx;
+                                    return;
+                                }
                             }
+                            --idx;
                         }
                     }
                     else {
                         // up to parent node
                         if ( pNode->pParent ) {
-                            idx = pNode->m_idx - 1;
+                            idx = pNode->idxParent - 1;
                             pNode = pNode->pParent;
                             nodeSize = pNode->pParent ? arrayNodeSize : headSize;
                         }
@@ -382,7 +389,7 @@ namespace cds { namespace intrusive {
         class reverse_bidirectional_iterator : protected bidirectional_iterator<IsConst>
         {
             typedef bidirectional_iterator<IsConst> base_class;
-            friend class MultLevelHashSet;
+            friend class MultiLevelHashSet;
 
         public:
             typedef typename base_class::value_ptr value_ptr;
@@ -403,13 +410,13 @@ namespace cds { namespace intrusive {
                 return *this;
             }
 
-            bidirectional_iterator& operator++()
+            reverse_bidirectional_iterator& operator++()
             {
                 base_class::backward();
                 return *this;
             }
 
-            bidirectional_iterator& operator--()
+            reverse_bidirectional_iterator& operator--()
             {
                 base_class::forward();
                 return *this;
@@ -430,16 +437,16 @@ namespace cds { namespace intrusive {
                 base_class::release();
             }
 
-            template <bool IsConst1, bool IsConst2>
-            friend bool operator ==(reverse_bidirectional_iterator<IsConst1> const& lhs, reverse_bidirectional_iterator<IsConst2> const& rhs)
+            template <bool IsConst2>
+            bool operator ==(reverse_bidirectional_iterator<IsConst2> const& rhs) const
             {
-                return lhs.m_pNode == rhs.m_pNode && lhs.m_idx == rhs.m_idx && lhs.m_set == rhs.m_set;
+                return base_class::operator==( rhs );
             }
 
-            template <bool IsConst1, bool IsConst2>
-            friend bool operator !=(reverse_bidirectional_iterator<IsConst1> const& lhs, reverse_bidirectional_iterator<IsConst2> const& rhs)
+            template <bool IsConst2>
+            bool operator !=(reverse_bidirectional_iterator<IsConst2> const& rhs)
             {
-                return !( lhs == rhs );
+                return !( *this == rhs );
             }
 
         private:

diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h
index d882c6a2b9c6735a175c053fbbc270e24be1d55f..3e417486471ec78c9a9031b9d0f79f80b540c22d 100644 (file)
--- a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h
+++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset.h
@@ -25,12 +25,14 @@ namespace set {
             unsigned int nInsertCall;
             unsigned int nFindCall;
             unsigned int nEraseCall;
+            mutable unsigned int nIteratorCall;
 
             Item()
                 : nDisposeCount(0)
                 , nInsertCall(0)
                 , nFindCall(0)
                 , nEraseCall(0)
+                , nIteratorCall(0)
             {}
         };
 
@@ -51,13 +53,13 @@ namespace set {
             }
         };
 
-        template <typename Set>
-        void test_hp()
+        template <typename Set, typename Hash>
+        void test_hp( size_t nHeadBits, size_t nArrayBits )
         {
             typedef typename Set::hash_type hash_type;
             typedef typename Set::value_type value_type;
 
-            std::hash<hash_type> hasher;
+            Hash hasher;
 
             size_t const arrCapacity = 1000;
             std::vector< value_type > arrValue;
@@ -68,9 +70,10 @@ namespace set {
             }
             CPPUNIT_ASSERT( arrValue.size() == arrCapacity );
 
-            Set s( 4, 2 );
-            CPPUNIT_ASSERT(s.head_size() == 16 );
-            CPPUNIT_ASSERT(s.array_node_size() == 4 );
+            Set s( nHeadBits, nArrayBits );
+            CPPUNIT_MSG("Array size: head=" << s.head_size() << ", array_node=" << s.array_node_size());
+            CPPUNIT_ASSERT(s.head_size() >= (size_t(1) << nHeadBits));
+            CPPUNIT_ASSERT(s.array_node_size() == (size_t(1) << nArrayBits));
 
             // insert() test
             CPPUNIT_ASSERT(s.size() == 0 );
@@ -87,6 +90,49 @@ namespace set {
             CPPUNIT_ASSERT(s.size() == arrCapacity );
             CPPUNIT_ASSERT( !s.empty() );
 
+            // Iterator test
+            {
+                typedef typename Set::iterator iterator;
+                for ( iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it )
+                    ++(it->nIteratorCall);
+                for ( auto& el : arrValue ) {
+                    CPPUNIT_ASSERT( el.nIteratorCall == 1 );
+                    el.nIteratorCall = 0;
+                }
+            }
+
+            {
+                // Const iterator test
+                for ( typename Set::const_iterator it = s.cbegin(), itEnd = s.cend(); it != itEnd; ++it )
+                    (*it).nIteratorCall += 1;
+                for ( auto& el : arrValue ) {
+                    CPPUNIT_ASSERT( el.nIteratorCall == 1 );
+                    el.nIteratorCall = 0;
+                }
+            }
+
+            {
+                // Reverse iterator test
+                for ( typename Set::reverse_iterator it = s.rbegin(), itEnd = s.rend(); it != itEnd; ++it )
+                    it->nIteratorCall += 1;
+                for ( auto& el : arrValue ) {
+                    CPPUNIT_ASSERT( el.nIteratorCall == 1 );
+                    el.nIteratorCall = 0;
+                }
+            }
+
+            {
+                // Reverse const iterator test
+                for ( typename Set::const_reverse_iterator it = s.crbegin(), itEnd = s.crend(); it != itEnd; ++it ) {
+                    (*it).nIteratorCall += 1;
+                    it.release();
+                }
+                for ( auto& el : arrValue ) {
+                    CPPUNIT_ASSERT( el.nIteratorCall == 1 );
+                    el.nIteratorCall = 0;
+                }
+            }
+
             // update() exists test
             for ( auto& el : arrValue ) {
                 bool bOp, bInsert;
@@ -227,10 +273,14 @@ namespace set {
 
         void hp_stdhash();
         void hp_stdhash_stat();
+        void hp_stdhash_5_3();
+        void hp_stdhash_5_3_stat();
 
         CPPUNIT_TEST_SUITE(IntrusiveMultiLevelHashSetHdrTest)
             CPPUNIT_TEST(hp_stdhash)
             CPPUNIT_TEST(hp_stdhash_stat)
+            CPPUNIT_TEST(hp_stdhash_5_3)
+            CPPUNIT_TEST(hp_stdhash_5_3_stat)
         CPPUNIT_TEST_SUITE_END()
     };
 } // namespace set

diff --git a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_hp.cpp b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_hp.cpp
index 83f2fd3ab3b37b1bec4be02112daa2cc06009c59..43822e29aedf091f58cd13465a0a59f505e54539 100644 (file)
--- a/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_hp.cpp
+++ b/tests/test-hdr/set/hdr_intrusive_multilevel_hashset_hp.cpp
@@ -19,7 +19,8 @@ namespace set {
             typedef item_disposer disposer;
         };
         typedef ci::MultiLevelHashSet< gc_type, Item<hash_type>, traits > set_type;
-        test_hp<set_type>();
+        static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" );
+        test_hp<set_type, std::hash<hash_type>>(4, 2);
 
         typedef ci::MultiLevelHashSet< 
             gc_type, 
@@ -29,7 +30,7 @@ namespace set {
                 , ci::opt::disposer< item_disposer >
             >::type
         > set_type2;
-        test_hp<set_type2>();
+        test_hp<set_type2, std::hash<hash_type>>(4, 2);
     }
 
     void IntrusiveMultiLevelHashSetHdrTest::hp_stdhash_stat()
@@ -43,7 +44,8 @@ namespace set {
             typedef ci::multilevel_hashset::stat<> stat;
         };
         typedef ci::MultiLevelHashSet< gc_type, Item<hash_type>, traits > set_type;
-        test_hp<set_type>();
+        static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" );
+        test_hp<set_type, std::hash<hash_type>>(4, 2);
 
         typedef ci::MultiLevelHashSet< 
             gc_type, 
@@ -54,7 +56,57 @@ namespace set {
                 ,co::stat< ci::multilevel_hashset::stat<>>
             >::type
         > set_type2;
-        test_hp<set_type2>();
+        test_hp<set_type2, std::hash<hash_type>>(4, 2);
+    }
+
+    void IntrusiveMultiLevelHashSetHdrTest::hp_stdhash_5_3()
+    {
+        typedef size_t hash_type;
+
+        struct traits: public ci::multilevel_hashset::traits
+        {
+            typedef get_hash<hash_type> hash_accessor;
+            typedef item_disposer disposer;
+        };
+        typedef ci::MultiLevelHashSet< gc_type, Item<hash_type>, traits > set_type;
+        static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" );
+        test_hp<set_type, std::hash<hash_type>>(5, 3);
+
+        typedef ci::MultiLevelHashSet< 
+            gc_type, 
+            Item<hash_type>, 
+            typename ci::multilevel_hashset::make_traits<
+                ci::multilevel_hashset::hash_accessor< get_hash<hash_type>>
+                , ci::opt::disposer< item_disposer >
+            >::type
+        > set_type2;
+        test_hp<set_type2, std::hash<hash_type>>(5, 3);
+    }
+
+    void IntrusiveMultiLevelHashSetHdrTest::hp_stdhash_5_3_stat()
+    {
+        typedef size_t hash_type;
+
+        struct traits: public ci::multilevel_hashset::traits
+        {
+            typedef get_hash<hash_type> hash_accessor;
+            typedef item_disposer disposer;
+            typedef ci::multilevel_hashset::stat<> stat;
+        };
+        typedef ci::MultiLevelHashSet< gc_type, Item<hash_type>, traits > set_type;
+        static_assert(std::is_same< typename set_type::hash_type, size_t>::value, "set::hash_type != size_t!!!" );
+        test_hp<set_type, std::hash<hash_type>>(5, 3);
+
+        typedef ci::MultiLevelHashSet< 
+            gc_type, 
+            Item<hash_type>, 
+            typename ci::multilevel_hashset::make_traits<
+                ci::multilevel_hashset::hash_accessor< get_hash<hash_type>>
+                , ci::opt::disposer< item_disposer >
+                ,co::stat< ci::multilevel_hashset::stat<>>
+            >::type
+        > set_type2;
+        test_hp<set_type2, std::hash<hash_type>>(5, 3);
     }
 
 } // namespace set