Added internal statistics to MichaelList, IterableList
authorkhizmax <libcds.dev@gmail.com>
Mon, 25 Jul 2016 05:53:36 +0000 (08:53 +0300)
committerkhizmax <libcds.dev@gmail.com>
Mon, 25 Jul 2016 05:53:36 +0000 (08:53 +0300)
39 files changed:
cds/container/details/make_michael_kvlist.h
cds/container/details/make_michael_list.h
cds/container/details/michael_list_base.h
cds/container/impl/michael_kvlist.h
cds/container/impl/michael_list.h
cds/container/michael_kvlist_nogc.h
cds/container/michael_kvlist_rcu.h
cds/container/michael_list_nogc.h
cds/container/michael_list_rcu.h
cds/intrusive/details/iterable_list_base.h
cds/intrusive/details/michael_list_base.h
cds/intrusive/details/michael_set_base.h
cds/intrusive/impl/iterable_list.h
cds/intrusive/impl/michael_list.h
cds/intrusive/michael_list_nogc.h
cds/intrusive/michael_list_rcu.h
cds/intrusive/michael_set.h
projects/Win/vc14/cds.vcxproj.filters
projects/Win/vc14/gtest-intrusive-set.vcxproj
projects/Win/vc14/gtest-intrusive-set.vcxproj.filters
test/unit/intrusive-set/CMakeLists.txt
test/unit/intrusive-set/intrusive_michael_iterable_dhp.cpp [new file with mode: 0644]
test/unit/intrusive-set/intrusive_michael_iterable_hp.cpp [new file with mode: 0644]
test/unit/intrusive-set/intrusive_michael_michael_dhp.cpp
test/unit/intrusive-set/intrusive_michael_michael_hp.cpp
test/unit/intrusive-set/test_intrusive_michael_iterable.h [new file with mode: 0644]
test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h [new file with mode: 0644]
test/unit/list/intrusive_michael_dhp.cpp
test/unit/list/intrusive_michael_hp.cpp
test/unit/list/kv_michael_dhp.cpp
test/unit/list/kv_michael_hp.cpp
test/unit/list/kv_michael_nogc.cpp
test/unit/list/michael_dhp.cpp
test/unit/list/michael_hp.cpp
test/unit/list/michael_nogc.cpp
test/unit/list/test_intrusive_iterable_list.h
test/unit/list/test_intrusive_michael_rcu.h
test/unit/list/test_kv_michael_rcu.h
test/unit/list/test_michael_rcu.h

index b151306..385a2c9 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_MAKE_MICHAEL_KVLIST_H
index 20fea0d..e779c60 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_MAKE_MICHAEL_LIST_H
index 7169c35..2a64ba4 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_LIST_BASE_H
@@ -41,10 +41,23 @@ namespace cds { namespace container {
     /** @ingroup cds_nonintrusive_helper
     */
     namespace michael_list {
+
+        /// \p MichaelList internal statistics, see \p cds::intrusive::michael_list::stat
+        template <typename EventCounter = cds::atomicity::event_counter>
+        using stat = cds::intrusive::michael_list::stat< EventCounter >;
+
+        /// \p MichaelList empty internal statistics, see \p cds::intrusive::michael_list::empty_stat
+        typedef cds::intrusive::michael_list::empty_stat empty_stat;
+
+        //@cond
+        template <typename Stat = michael_list::stat<>>
+        using wrapped_stat = cds::intrusive::michael_list::wrapped_stat< Stat >;
+        //@endif
+
         /// MichaelList traits
         struct traits
         {
-            typedef CDS_DEFAULT_ALLOCATOR   allocator       ;   ///< allocator used to allocate new node
+            typedef CDS_DEFAULT_ALLOCATOR   allocator;   ///< allocator used to allocate new node
 
             /// Key comparison functor
             /**
@@ -64,6 +77,13 @@ namespace cds { namespace container {
             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
             typedef atomicity::empty_item_counter     item_counter;
 
+            /// Internal statistics
+            /**
+                By default, internal statistics is disabled (\p michael_list::empty_stat).
+                Use \p michael_list::stat to enable it.
+            */
+            typedef empty_stat                      stat;
+
             /// C++ memory ordering model
             /**
                 Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
@@ -86,6 +106,20 @@ namespace cds { namespace container {
 
         /// Metafunction converting option list to \p michael_list::traits
         /**
+            Supported \p Options are:
+            - \p opt::compare - key comparison functor. No default functor is provided.
+                If the option is not specified, the \p opt::less is used.
+            - \p opt::less - specifies binary predicate used for key comparison. Default is \p std::less<T>.
+            - \p opt::allocator - an allocator, default is \p CDS_DEFAULT_ALLOCATOR
+            - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
+            - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
+                 To enable item counting use \p atomicity::item_counter.
+            - \p opt::stat - internal statistics. By default, it is disabled (\p michael_list::empty_stat).
+                To enable it use \p michael_list::stat
+            - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+                or \p opt::v::sequential_consistent (sequentially consistent memory model).
+            - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
+                Default is \p opt::v::rcu_throw_deadlock
         */
         template <typename... Options>
         struct make_traits {
index 28f18ef..37f7a49 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_IMPL_MICHAEL_KVLIST_H
@@ -136,6 +136,7 @@ namespace cds { namespace container {
         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
+        typedef typename base_class::stat         stat;           ///< Internal statistics
 
         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 
@@ -357,7 +358,14 @@ namespace cds { namespace container {
         MichaelKVList()
         {}
 
-        /// List desctructor
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelKVList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
+        /// List destructor
         /**
             Clears the list
         */
@@ -766,6 +774,12 @@ namespace cds { namespace container {
             base_class::clear();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return base_class::statistics();
+        }
+
     protected:
         //@cond
         bool insert_node_at( head_type& refHead, node_type * pNode )
index 514dbfd..27c87b9 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_IMPL_MICHAEL_LIST_H
@@ -136,6 +136,7 @@ namespace cds { namespace container {
         typedef typename base_class::item_counter   item_counter;   ///< Item counting policy used
         typedef typename maker::key_comparator      key_comparator; ///< key comparison functor
         typedef typename base_class::memory_model   memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
+        typedef typename base_class::stat           stat;           ///< Internal statistics
 
         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount; ///< Count of hazard pointer required for the algorithm
 
@@ -335,6 +336,13 @@ namespace cds { namespace container {
         MichaelList()
         {}
 
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
         /// List destructor
         /**
             Clears the list
@@ -733,6 +741,12 @@ namespace cds { namespace container {
             base_class::clear();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return base_class::statistics();
+        }
+
     protected:
         //@cond
         bool insert_node( node_type * pNode )
index 53f71b0..89974bf 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_MICHAEL_KVLIST_NOGC_H
@@ -112,6 +112,7 @@ namespace cds { namespace container {
         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
+        typedef typename base_class::stat         stat;           ///< Internal statistics
 
     protected:
         //@cond
@@ -346,7 +347,14 @@ namespace cds { namespace container {
         MichaelKVList()
         {}
 
-        /// List desctructor
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelKVList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
+        /// List destructor
         /**
             Clears the list
         */
@@ -519,6 +527,12 @@ namespace cds { namespace container {
             return base_class::size();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return base_class::statistics();
+        }
+
         /// Clears the list
         void clear()
         {
index 175cc23..2dbe9ff 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_MICHAEL_KVLIST_RCU_H
@@ -138,6 +138,7 @@ namespace cds { namespace container {
         typedef typename base_class::item_counter item_counter;   ///< Item counting policy
         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See \p michael_list::traits::memory_model
+        typedef typename base_class::stat         stat;           ///< Internal statistics
         typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
 
         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
@@ -367,7 +368,14 @@ namespace cds { namespace container {
         MichaelKVList()
         {}
 
-        /// List desctructor
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelKVList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
+        /// List destructor
         /**
             Clears the list
         */
@@ -817,6 +825,12 @@ namespace cds { namespace container {
             return base_class::size();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return base_class::statistics();
+        }
+
         /// Clears the list
         /**
             Post-condition: the list is empty
index b7fbbf6..1bf897c 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_MICHAEL_LIST_NOGC_H
@@ -98,6 +98,7 @@ namespace cds { namespace container {
         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
+        typedef typename base_class::stat         stat;           ///< Internal statistics
 
     protected:
         //@cond
@@ -301,7 +302,14 @@ namespace cds { namespace container {
         MichaelList()
         {}
 
-        /// List desctructor
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
+        /// List destructor
         /**
             Clears the list
         */
@@ -418,6 +426,12 @@ namespace cds { namespace container {
             return base_class::size();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return base_class::statistics();
+        }
+
         /// Clears the list
         void clear()
         {
index 61d1623..861da79 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_MICHAEL_LIST_RCU_H
@@ -148,6 +148,7 @@ namespace cds { namespace container {
         typedef typename base_class::item_counter item_counter;   ///< Item counting policy used
         typedef typename maker::key_comparator    key_comparator; ///< key comparison functor
         typedef typename base_class::memory_model memory_model;   ///< Memory ordering. See cds::opt::memory_model option
+        typedef typename base_class::stat         stat;           ///< Internal statistics
         typedef typename base_class::rcu_check_deadlock rcu_check_deadlock ; ///< RCU deadlock checking policy
 
         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
@@ -361,6 +362,13 @@ namespace cds { namespace container {
         MichaelList()
         {}
 
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
         /// List destructor
         /**
             Clears the list
@@ -777,6 +785,12 @@ namespace cds { namespace container {
             return base_class::size();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return base_class::statistics();
+        }
+
         /// Clears the list
         void clear()
         {
index 7ef00bd..824d239 100644 (file)
@@ -245,6 +245,21 @@ namespace cds { namespace intrusive {
     class IterableList;
     //@endcond
 
+    //@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
+        };
+    };
+    //@endcond
 
 }}   // namespace cds::intrusive
 
index 2b72b26..b6cc2ca 100644 (file)
@@ -196,6 +196,101 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
+
+        /// \p MichaelList internal statistics
+        template <typename EventCounter = cds::atomicity::event_counter>
+        struct stat {
+            typedef EventCounter event_counter; ///< Event counter type
+
+            event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
+            event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
+            event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
+            event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
+            event_counter   m_nUpdateExisting;  ///< Number of existing item updates
+            event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
+            event_counter   m_nUpdateRetry;     ///< Number of attempts to \p update() the item
+            event_counter   m_nUpdateMarked;    ///< Number of attempts to \p update() logically deleted (marked) items
+            event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
+            event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
+            event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
+            event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
+            event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
+
+            event_counter   m_nHelpingSuccess;  ///< Number of successful help attempts to remove marked item during searching
+            event_counter   m_nHelpingFailed;   ///< Number if failed help attempts to remove marked item during searching
+
+            //@cond
+            void onInsertSuccess()      { ++m_nInsertSuccess;   }
+            void onInsertFailed()       { ++m_nInsertFailed;    }
+            void onInsertRetry()        { ++m_nInsertRetry;     }
+            void onUpdateNew()          { ++m_nUpdateNew;       }
+            void onUpdateExisting()     { ++m_nUpdateExisting;  }
+            void onUpdateFailed()       { ++m_nUpdateFailed;    }
+            void onUpdateRetry()        { ++m_nUpdateRetry;     }
+            void onUpdateMarked()       { ++m_nUpdateMarked;    }
+            void onEraseSuccess()       { ++m_nEraseSuccess;    }
+            void onEraseFailed()        { ++m_nEraseFailed;     }
+            void onEraseRetry()         { ++m_nEraseRetry;      }
+            void onFindSuccess()        { ++m_nFindSuccess;     }
+            void onFindFailed()         { ++m_nFindFailed;      }
+
+            void onHelpingSuccess()     { ++m_nHelpingSuccess;  }
+            void onHelpingFailed()      { ++m_nHelpingFailed;   }
+            //@endcond
+        };
+
+        /// \p MichaelList empty internal statistics
+        struct empty_stat {
+            //@cond
+            void onInsertSuccess()              const {}
+            void onInsertFailed()               const {}
+            void onInsertRetry()                const {}
+            void onUpdateNew()                  const {}
+            void onUpdateExisting()             const {}
+            void onUpdateFailed()               const {}
+            void onUpdateRetry()                const {}
+            void onUpdateMarked()               const {}
+            void onEraseSuccess()               const {}
+            void onEraseFailed()                const {}
+            void onEraseRetry()                 const {}
+            void onFindSuccess()                const {}
+            void onFindFailed()                 const {}
+
+            void onHelpingSuccess()             const {}
+            void onHelpingFailed()              const {}
+            //@endcond
+        };
+
+        //@cond
+        template <typename Stat = michael_list::stat<>>
+        struct wrapped_stat {
+            typedef Stat stat_type;
+
+            wrapped_stat( stat_type& st )
+                : m_stat( st )
+            {}
+
+            void onInsertSuccess()      { m_stat.onInsertSuccess();     }
+            void onInsertFailed()       { m_stat.onInsertFailed();      }
+            void onInsertRetry()        { m_stat.onInsertRetry();       }
+            void onUpdateNew()          { m_stat.onUpdateNew();         }
+            void onUpdateExisting()     { m_stat.onUpdateExisting();    }
+            void onUpdateFailed()       { m_stat.onUpdateFailed();      }
+            void onUpdateRetry()        { m_stat.onUpdateRetry();       }
+            void onUpdateMarked()       { m_stat.onUpdateMarked();      }
+            void onEraseSuccess()       { m_stat.onEraseSuccess();      }
+            void onEraseFailed()        { m_stat.onEraseFailed();       }
+            void onEraseRetry()         { m_stat.onEraseRetry();        }
+            void onFindSuccess()        { m_stat.onFindSuccess();       }
+            void onFindFailed()         { m_stat.onFindFailed();        }
+
+            void onHelpingSuccess()     { m_stat.onHelpingSuccess();    }
+            void onHelpingFailed()      { m_stat.onHelpingFailed();     }
+
+            stat_type& m_stat;
+        };
+        //@endcond
+
         /// MichaelList traits
         struct traits
         {
@@ -224,7 +319,14 @@ namespace cds { namespace intrusive {
             typedef opt::v::empty_disposer          disposer;
 
             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
-            typedef atomicity::empty_item_counter     item_counter;
+            typedef atomicity::empty_item_counter   item_counter;
+
+            /// Internal statistics
+            /**
+                By default, internal statistics is disabled (\p michael_list::empty_stat).
+                Use \p michael_list::stat to enable it.
+            */
+            typedef empty_stat                      stat;
 
             /// Link fields checking feature
             /**
@@ -260,6 +362,8 @@ namespace cds { namespace intrusive {
             - \p opt::link_checker - the type of node's link fields checking. Default is \p opt::debug_check_link
             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
                  To enable item counting use \p atomicity::item_counter.
+            - \p opt::stat - internal statistics. By default, it is disabled (\p michael_list::empty_stat).
+                To enable it use \p michael_list::stat
             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_MichaelList_rcu "RCU-based MichaelList"
index 2e7eef9..64c08d2 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_INTRUSIVE_DETAILS_MICHAEL_SET_BASE_H
index 00e2023..21f3d5f 100644 (file)
@@ -466,9 +466,9 @@ namespace cds { namespace intrusive {
             return update_at( m_pHead, val, func, bInsert );
         }
 
-        /// Updates the node
+        /// Insert or update
         /**
-            The operation performs inserting or changing data with lock-free manner.
+            The operation performs inserting or updating data with lock-free manner.
 
             If the item \p val is not found in the list, then \p val is inserted
             iff \p bInsert is \p true.
@@ -479,7 +479,7 @@ namespace cds { namespace intrusive {
             \p second is \p true if \p val has been added or \p false if the item with that key
             already in the list.
         */
-        std::pair<bool, bool> update( value_type& val, bool bInsert = true )
+        std::pair<bool, bool> upsert( value_type& val, bool bInsert = true )
         {
             return update_at( m_pHead, val, []( value_type&, value_type* ) {}, bInsert );
         }
@@ -832,6 +832,12 @@ namespace cds { namespace intrusive {
             return m_ItemCounter.value();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return m_Stat;
+        }
+
     protected:
         //@cond
 #if 0
index 55c778e..97bf868 100644 (file)
@@ -201,6 +201,7 @@ namespace cds { namespace intrusive {
 #   endif
 
         typedef typename traits::disposer  disposer; ///< disposer used
+        typedef typename traits::stat      stat;     ///< Internal statistics
         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
         typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
 
@@ -231,8 +232,9 @@ namespace cds { namespace intrusive {
 
         typedef atomic_node_ptr     auxiliary_head;   ///< Auxiliary head type (for split-list support)
 
-        atomic_node_ptr     m_pHead;        ///< Head pointer
-        item_counter        m_ItemCounter;  ///< Item counter
+        atomic_node_ptr m_pHead;        ///< Head pointer
+        item_counter    m_ItemCounter;  ///< Item counter
+        stat            m_Stat;         ///< Internal statistics
 
         //@cond
         /// Position pointer for item search
@@ -518,6 +520,14 @@ namespace cds { namespace intrusive {
             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
         }
 
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelList( Stat& st )
+            : m_pHead( nullptr )
+            , m_Stat( st )
+        {}
+        //@endcond
+
         /// Destroys the list object
         ~MichaelList()
         {
@@ -925,13 +935,19 @@ namespace cds { namespace intrusive {
             this function always returns 0.
 
             @note Even if you use real item counter and it returns 0, this fact does not mean that the list
-            is empty. To check list emptyness use \p empty() method.
+            is empty. To check list emptiness use \p empty() method.
         */
         size_t size() const
         {
             return m_ItemCounter.value();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return m_Stat;
+        }
+
     protected:
         //@cond
         // split-list support
@@ -957,16 +973,18 @@ namespace cds { namespace intrusive {
             position pos;
 
             while ( true ) {
-                if ( search( refHead, val, pos, key_comparator()))
+                if ( search( refHead, val, pos, key_comparator())) {
+                    m_Stat.onInsertFailed();
                     return false;
+                }
 
                 if ( link_node( pNode, pos )) {
                     ++m_ItemCounter;
+                    m_Stat.onInsertSuccess();
                     return true;
                 }
 
-                // clear next field
-                pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+                m_Stat.onInsertRetry();
             }
         }
 
@@ -977,19 +995,21 @@ namespace cds { namespace intrusive {
             position pos;
 
             while ( true ) {
-                if ( search( refHead, val, pos, key_comparator()))
+                if ( search( refHead, val, pos, key_comparator())) {
+                    m_Stat.onInsertFailed();
                     return false;
+                }
 
                 typename gc::Guard guard;
                 guard.assign( &val );
                 if ( link_node( pNode, pos )) {
                     f( val );
                     ++m_ItemCounter;
+                    m_Stat.onInsertSuccess();
                     return true;
                 }
 
-                // clear next field
-                pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+                m_Stat.onInsertRetry();
             }
         }
 
@@ -1003,27 +1023,32 @@ namespace cds { namespace intrusive {
                 if ( search( refHead, val, pos, key_comparator())) {
                     if ( cds_unlikely( pos.pCur->m_pNext.load(memory_model::memory_order_acquire).bits())) {
                         back_off()();
+                        m_Stat.onUpdateMarked();
                         continue;       // the node found is marked as deleted
                     }
                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur )) == 0 );
 
                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
+                    m_Stat.onUpdateExisting();
                     return std::make_pair( true, false );
                 }
                 else {
-                    if ( !bInsert )
+                    if ( !bInsert ) {
+                        m_Stat.onUpdateFailed();
                         return std::make_pair( false, false );
+                    }
 
                     typename gc::Guard guard;
                     guard.assign( &val );
                     if ( link_node( pNode, pos )) {
                         ++m_ItemCounter;
                         func( true, val, val );
+                        m_Stat.onUpdateNew();
                         return std::make_pair( true, true );
                     }
-                    // clear next field
-                    pNode->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
                 }
+
+                m_Stat.onUpdateRetry();
             }
         }
 
@@ -1036,14 +1061,21 @@ namespace cds { namespace intrusive {
                 if ( node_traits::to_value_ptr( *pos.pCur ) == &val ) {
                     if ( unlink_node( pos )) {
                         --m_ItemCounter;
+                        m_Stat.onEraseSuccess();
                         return true;
                     }
                     else
                         bkoff();
                 }
-                else
+                else {
+                    m_Stat.onUpdateFailed();
                     break;
+                }
+
+                m_Stat.onEraseRetry();
             }
+
+            m_Stat.onEraseFailed();
             return false;
         }
 
@@ -1055,11 +1087,16 @@ namespace cds { namespace intrusive {
                 if ( unlink_node( pos )) {
                     f( *node_traits::to_value_ptr( *pos.pCur ));
                     --m_ItemCounter;
+                    m_Stat.onEraseSuccess();
                     return true;
                 }
                 else
                     bkoff();
+
+                m_Stat.onEraseRetry();
             }
+
+            m_Stat.onEraseFailed();
             return false;
         }
 
@@ -1086,11 +1123,15 @@ namespace cds { namespace intrusive {
                 if ( unlink_node( pos )) {
                     dest.set( pos.guards.template get<value_type>( position::guard_current_item ));
                     --m_ItemCounter;
+                    m_Stat.onEraseSuccess();
                     return true;
                 }
                 else
                     bkoff();
+                m_Stat.onEraseRetry();
             }
+
+            m_Stat.onEraseFailed();
             return false;
         }
 
@@ -1098,7 +1139,13 @@ namespace cds { namespace intrusive {
         bool find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
         {
             position pos;
-            return search( refHead, val, pos, cmp );
+            if ( search( refHead, val, pos, cmp ) ) {
+                m_Stat.onFindSuccess();
+                return true;
+            }
+
+            m_Stat.onFindFailed();
+            return false;
         }
 
         template <typename Q, typename Compare, typename Func>
@@ -1107,8 +1154,11 @@ namespace cds { namespace intrusive {
             position pos;
             if ( search( refHead, val, pos, cmp )) {
                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
+                m_Stat.onFindSuccess();
                 return true;
             }
+
+            m_Stat.onFindFailed();
             return false;
         }
 
@@ -1118,8 +1168,11 @@ namespace cds { namespace intrusive {
             position pos;
             if ( search( refHead, val, pos, cmp )) {
                 guard.set( pos.guards.template get<value_type>( position::guard_current_item ));
+                m_Stat.onFindSuccess();
                 return true;
             }
+
+            m_Stat.onFindFailed();
             return false;
         }
 
@@ -1171,9 +1224,11 @@ namespace cds { namespace intrusive {
                     marked_node_ptr cur( pCur.ptr());
                     if ( cds_unlikely( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr()), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
                         retire_node( pCur.ptr());
+                        m_Stat.onHelpingSuccess();
                     }
                     else {
                         bkoff();
+                        m_Stat.onHelpingFailed();
                         goto try_again;
                     }
                 }
index 3e3920b..e7378a7 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_INTRUSIVE_MICHAEL_LIST_NOGC_H
@@ -35,7 +35,6 @@
 #include <cds/gc/nogc.h>
 #include <cds/details/make_const_type.h>
 
-
 namespace cds { namespace intrusive {
 
     namespace michael_list {
@@ -96,11 +95,14 @@ namespace cds { namespace intrusive {
         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
         typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
 
-        typedef typename traits::back_off     back_off;      ///< back-off strategy
-        typedef typename traits::item_counter item_counter;  ///< Item counting policy used
-        typedef typename traits::memory_model  memory_model; ///< Memory ordering. See cds::opt::memory_model option
+        typedef typename traits::back_off     back_off;     ///< back-off strategy
+        typedef typename traits::item_counter item_counter; ///< Item counting policy used
+        typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
+        typedef typename traits::stat         stat;         ///< Internal statistics
 
         //@cond
+        static_assert((std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type");
+
         // Rebind traits (split-list support)
         template <typename... Options>
         struct rebind_traits {
@@ -118,6 +120,7 @@ namespace cds { namespace intrusive {
 
         atomic_node_ptr     m_pHead;        ///< Head pointer
         item_counter        m_ItemCounter;  ///< Item counter
+        stat                m_Stat;         ///< Internal statistics
 
         //@cond
         /// Position pointer for item search
@@ -309,9 +312,15 @@ namespace cds { namespace intrusive {
         /// Default constructor initializes empty list
         MichaelList()
             : m_pHead( nullptr )
-        {
-            static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
-        }
+        {}
+
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelList( Stat& st )
+            : m_pHead( nullptr )
+            , m_Stat( st )
+        {}
+        //@endcond
 
         /// Destroys the list objects
         ~MichaelList()
@@ -513,6 +522,12 @@ namespace cds { namespace intrusive {
             return m_ItemCounter.value();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return m_Stat;
+        }
+
     protected:
         //@cond
         // split-list support
@@ -537,13 +552,18 @@ namespace cds { namespace intrusive {
             position pos;
 
             while ( true ) {
-                if ( search( refHead, val, key_comparator(), pos ) )
+                if ( search( refHead, val, key_comparator(), pos )) {
+                    m_Stat.onInsertFailed();
                     return false;
+                }
 
                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
                     ++m_ItemCounter;
+                    m_Stat.onInsertSuccess();
                     return true;
                 }
+
+                m_Stat.onInsertRetry();
             }
         }
 
@@ -564,18 +584,24 @@ namespace cds { namespace intrusive {
                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 
                     func( false, *node_traits::to_value_ptr( *pos.pCur ) , val );
+                    m_Stat.onUpdateExisting();
                     return std::make_pair( iterator( pos.pCur ), false );
                 }
                 else {
-                    if ( !bAllowInsert )
+                    if ( !bAllowInsert ) {
+                        m_Stat.onUpdateFailed();
                         return std::make_pair( end(), false );
+                    }
 
                     if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
                         ++m_ItemCounter;
                         func( true, val , val );
+                        m_Stat.onUpdateNew();
                         return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
                     }
                 }
+
+                m_Stat.onUpdateRetry();
             }
         }
 
@@ -594,8 +620,11 @@ namespace cds { namespace intrusive {
             if ( search( refHead, val, cmp, pos ) ) {
                 assert( pos.pCur != nullptr );
                 f( *node_traits::to_value_ptr( *pos.pCur ), val );
+                m_Stat.onFindSuccess();
                 return true;
             }
+
+            m_Stat.onFindFailed();
             return false;
         }
 
@@ -603,8 +632,12 @@ namespace cds { namespace intrusive {
         value_type * find_at( atomic_node_ptr& refHead, Q const& val, Compare cmp )
         {
             iterator it = find_at_( refHead, val, cmp );
-            if ( it != end() )
+            if ( it != end() ) {
+                m_Stat.onFindSuccess();
                 return &*it;
+            }
+
+            m_Stat.onFindFailed();
             return nullptr;
         }
 
@@ -615,8 +648,11 @@ namespace cds { namespace intrusive {
 
             if ( search( refHead, val, cmp, pos ) ) {
                 assert( pos.pCur != nullptr );
+                m_Stat.onFindSuccess();
                 return iterator( pos.pCur );
             }
+
+            m_Stat.onFindFailed();
             return end();
         }
 
index 2b9ae89..5267426 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_INTRUSIVE_MICHAEL_LIST_RCU_H
@@ -118,11 +118,12 @@ namespace cds { namespace intrusive {
         typedef typename get_node_traits< value_type, node_type, hook>::type node_traits ;    ///< node traits
         typedef typename michael_list::get_link_checker< node_type, traits::link_checker >::type link_checker;   ///< link checker
 
-        typedef cds::urcu::gc<RCU>                     gc;           ///< RCU schema
-        typedef typename traits::back_off              back_off;     ///< back-off strategy
-        typedef typename traits::item_counter          item_counter; ///< Item counting policy used
-        typedef typename traits::memory_model          memory_model; ///< Memory ordering. See cds::opt::memory_model option
-        typedef typename traits::rcu_check_deadlock    rcu_check_deadlock; ///< Deadlock checking policy
+        typedef cds::urcu::gc<RCU>                  gc;           ///< RCU schema
+        typedef typename traits::back_off           back_off;     ///< back-off strategy
+        typedef typename traits::item_counter       item_counter; ///< Item counting policy used
+        typedef typename traits::memory_model       memory_model; ///< Memory ordering. See cds::opt::memory_model option
+        typedef typename traits::rcu_check_deadlock rcu_check_deadlock; ///< Deadlock checking policy
+        typedef typename traits::stat               stat;     ///< Internal statistics
 
         typedef typename gc::scoped_lock    rcu_lock ;  ///< RCU scoped lock
         static CDS_CONSTEXPR const bool c_bExtractLockExternal = false; ///< Group of \p extract_xxx functions do not require external locking
@@ -140,12 +141,13 @@ namespace cds { namespace intrusive {
         //@endcond
 
     protected:
-        typedef typename node_type::marked_ptr         marked_node_ptr ; ///< Marked node pointer
-        typedef typename node_type::atomic_marked_ptr  atomic_node_ptr ; ///< Atomic node pointer
-        typedef atomic_node_ptr                 auxiliary_head      ;   ///< Auxiliary head type (for split-list support)
+        typedef typename node_type::marked_ptr        marked_node_ptr; ///< Marked node pointer
+        typedef typename node_type::atomic_marked_ptr atomic_node_ptr; ///< Atomic node pointer
+        typedef atomic_node_ptr                       auxiliary_head;  ///< Auxiliary head type (for split-list support)
 
-        atomic_node_ptr     m_pHead         ;   ///< Head pointer
-        item_counter        m_ItemCounter   ;   ///< Item counter
+        atomic_node_ptr m_pHead;        ///< Head pointer
+        item_counter    m_ItemCounter;  ///< Item counter
+        stat            m_Stat;         ///< Internal statistics
 
     protected:
         //@cond
@@ -440,6 +442,14 @@ namespace cds { namespace intrusive {
             static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
         }
 
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelList( Stat& st )
+            : m_pHead( nullptr )
+            , m_Stat( st )
+        {}
+        //@endcond
+
         /// Destroy list
         ~MichaelList()
         {
@@ -897,6 +907,11 @@ namespace cds { namespace intrusive {
             return m_ItemCounter.value();
         }
 
+        /// Returns const reference to internal statistics
+        stat const& statistics() const
+        {
+            return m_Stat;
+        }
     protected:
         //@cond
         // split-list support
@@ -933,17 +948,21 @@ namespace cds { namespace intrusive {
             {
                 rcu_lock l;
                 while ( true ) {
-                    if ( search( refHead, val, pos, key_comparator()))
+                    if ( search( refHead, val, pos, key_comparator())) {
+                        m_Stat.onInsertFailed();
                         return false;
+                    }
 
                     if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
                         f( val );
                         ++m_ItemCounter;
+                        m_Stat.onInsertSuccess();
                         return true;
                     }
 
                     // clear next field
                     node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+                    m_Stat.onInsertRetry();
                 }
             }
 
@@ -987,15 +1006,19 @@ namespace cds { namespace intrusive {
             for (;;) {
                 {
                     rcu_lock l;
-                    if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val )
+                    if ( !search( refHead, val, pos, key_comparator() ) || node_traits::to_value_ptr( *pos.pCur ) != &val ) {
+                        m_Stat.onEraseFailed();
                         return false;
+                    }
                     if ( !unlink_node( pos, erase_mask )) {
                         bkoff();
+                        m_Stat.onEraseRetry();
                         continue;
                     }
                 }
 
                 --m_ItemCounter;
+                m_Stat.onEraseSuccess();
                 return true;
             }
         }
@@ -1010,18 +1033,23 @@ namespace cds { namespace intrusive {
             for (;;) {
                 {
                     rcu_lock l;
-                    if ( !search( pos.refHead, val, pos, cmp ) )
+                    if ( !search( pos.refHead, val, pos, cmp ) ) {
+                        m_Stat.onEraseFailed();
                         return false;
+                    }
+
                     // store pCur since it may be changed by unlink_node() slow path
                     pDel = pos.pCur;
                     if ( !unlink_node( pos, erase_mask )) {
                         bkoff();
+                        m_Stat.onEraseRetry();
                         continue;
                     }
                 }
                 assert( pDel );
                 f( *node_traits::to_value_ptr( pDel ) );
                 --m_ItemCounter;
+                m_Stat.onEraseSuccess();
                 return true;
             }
         }
@@ -1051,18 +1079,23 @@ namespace cds { namespace intrusive {
             {
                 rcu_lock l;
                 for (;;) {
-                    if ( !search( refHead, val, pos, cmp ) )
+                    if ( !search( refHead, val, pos, cmp )) {
+                        m_Stat.onEraseFailed();
                         return nullptr;
+                    }
+
                     // store pCur since it may be changed by unlink_node() slow path
                     pExtracted = pos.pCur;
                     if ( !unlink_node( pos, extract_mask )) {
                         bkoff();
+                        m_Stat.onEraseRetry();
                         continue;
                     }
 
                     --m_ItemCounter;
                     value_type * pRet = node_traits::to_value_ptr( pExtracted );
                     assert( pExtracted->m_pDelChain == nullptr );
+                    m_Stat.onEraseSuccess();
                     return pRet;
                 }
             }
@@ -1078,10 +1111,13 @@ namespace cds { namespace intrusive {
                 if ( search( refHead, val, pos, cmp ) ) {
                     assert( pos.pCur != nullptr );
                     f( *node_traits::to_value_ptr( *pos.pCur ), val );
+                    m_Stat.onFindSuccess();
                     return true;
                 }
-                return false;
-            }
+           }
+
+            m_Stat.onFindFailed();
+            return false;
         }
 
         template <typename Q, typename Compare>
@@ -1102,8 +1138,12 @@ namespace cds { namespace intrusive {
 
             position pos( refHead );
 
-            if ( search( refHead, val, pos, cmp ))
+            if ( search( refHead, val, pos, cmp )) {
+                m_Stat.onFindSuccess();
                 return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos ));
+            }
+
+            m_Stat.onFindFailed();
             return raw_ptr( raw_ptr_disposer( pos ));
         }
         //@endcond
@@ -1150,8 +1190,10 @@ namespace cds { namespace intrusive {
                     if ( cds_likely( pPrev->compare_exchange_weak( pCur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))) {
                         if ( pNext.bits() == erase_mask )
                             link_to_remove_chain( pos, pCur.ptr() );
+                        m_Stat.onHelpingSuccess();
                     }
 
+                    m_Stat.onHelpingFailed();
                     goto try_again;
                 }
 
@@ -1177,16 +1219,20 @@ namespace cds { namespace intrusive {
             assert( gc::is_locked() );
 
             while ( true ) {
-                if ( search( pos.refHead, val, pos, key_comparator() ) )
+                if ( search( pos.refHead, val, pos, key_comparator() )) {
+                    m_Stat.onInsertFailed();
                     return false;
+                }
 
                 if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
                     ++m_ItemCounter;
+                    m_Stat.onInsertSuccess();
                     return true;
                 }
 
                 // clear next field
                 node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+                m_Stat.onInsertRetry();
             }
         }
 
@@ -1201,20 +1247,25 @@ namespace cds { namespace intrusive {
                     assert( key_comparator()( val, *node_traits::to_value_ptr( *pos.pCur ) ) == 0 );
 
                     func( false, *node_traits::to_value_ptr( *pos.pCur ), val );
+                    m_Stat.onUpdateExisting();
                     return std::make_pair( iterator( pos.pCur ), false );
                 }
                 else {
-                    if ( !bInsert )
+                    if ( !bInsert ) {
+                        m_Stat.onUpdateFailed();
                         return std::make_pair( end(), false );
+                    }
 
                     if ( link_node( node_traits::to_node_ptr( val ), pos ) ) {
                         ++m_ItemCounter;
                         func( true, val , val );
+                        m_Stat.onUpdateNew();
                         return std::make_pair( iterator( node_traits::to_node_ptr( val )), true );
                     }
 
                     // clear the next field
                     node_traits::to_node_ptr( val )->m_pNext.store( marked_node_ptr(), memory_model::memory_order_relaxed );
+                    m_Stat.onUpdateRetry();
                 }
             }
         }
@@ -1226,8 +1277,11 @@ namespace cds { namespace intrusive {
 
             if ( search( pos.refHead, val, pos, cmp ) ) {
                 assert( pos.pCur != nullptr );
+                m_Stat.onFindSuccess();
                 return const_iterator( pos.pCur );
             }
+
+            m_Stat.onFindFailed();
             return cend();
         }
         //@endcond
index b876b5e..327f09a 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_INTRUSIVE_MICHAEL_SET_H
@@ -33,6 +33,7 @@
 
 #include <cds/intrusive/details/michael_set_base.h>
 #include <cds/details/allocator.h>
+#include <cds/intrusive/details/iterable_list_base.h>
 
 namespace cds { namespace intrusive {
 
@@ -295,7 +296,7 @@ namespace cds { namespace intrusive {
         //@endcond
 
     public:
-    ///@name Forward iterators (only for debugging purpose)
+    ///@name Forward iterators
     //@{
         /// Forward iterator
         /**
@@ -303,19 +304,23 @@ namespace cds { namespace intrusive {
             - it has no post-increment operator
             - it iterates items in unordered fashion
             - The iterator cannot be moved across thread boundary because it may contain GC's guard that is thread-private GC data.
-            - Iterator ensures thread-safety even if you delete the item that iterator points to. 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.
 
-            @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.
+              
         */
-        typedef michael_set::details::iterator< bucket_type, false >    iterator;
+        typedef michael_set::details::iterator< 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< bucket_type, true > const_iterator;
 
         /// Returns a forward iterator addressing the first element in a set
         /**
@@ -323,7 +328,7 @@ namespace cds { namespace intrusive {
         */
         iterator begin()
         {
-            return iterator( m_Buckets[0].begin(), m_Buckets, m_Buckets + bucket_count() );
+            return iterator( m_Buckets[0].begin(), bucket_begin(), bucket_end() );
         }
 
         /// Returns an iterator that addresses the location succeeding the last element in a set
@@ -334,7 +339,7 @@ namespace cds { namespace intrusive {
         */
         iterator end()
         {
-            return iterator( m_Buckets[bucket_count() - 1].end(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
+            return iterator( m_Buckets[bucket_count() - 1].end(), bucket_end() + 1, bucket_end() );
         }
 
         /// Returns a forward const iterator addressing the first element in a set
@@ -364,13 +369,23 @@ namespace cds { namespace intrusive {
 
     private:
         //@cond
+        bucket_type * bucket_begin() const
+        {
+            return m_Buckets;
+        }
+
+        bucket_type * bucket_end() const
+        {
+            return m_Buckets + bucket_count();
+        }
+
         const_iterator get_const_begin() const
         {
-            return const_iterator( m_Buckets[0].cbegin(), m_Buckets, m_Buckets + bucket_count() );
+            return const_iterator( m_Buckets[0].cbegin(), bucket_begin(), bucket_end() );
         }
         const_iterator get_const_end() const
         {
-            return const_iterator( m_Buckets[bucket_count() - 1].cend(), m_Buckets + bucket_count() - 1, m_Buckets + bucket_count() );
+            return const_iterator( m_Buckets[bucket_count() - 1].cend(), bucket_end() - 1, bucket_end() );
         }
         //@endcond
 
@@ -456,28 +471,38 @@ namespace cds { namespace intrusive {
 
             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:
-            \code
-                struct functor {
-                    void operator()( bool bNew, value_type& item, value_type& val );
-                };
-            \endcode
-            with arguments:
-            - \p bNew - \p true if the item has been inserted, \p false otherwise
-            - \p item - item of the set
-            - \p val - argument \p val passed into the \p %update() function
-            If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
-            refers to the same thing.
 
-            The functor may change non-key fields of the \p item.
+            The functor signature depends of the type of \p OrderedList:
+
+            <b>for \p MichaelList, \p LazyList</b>
+                \code
+                    struct functor {
+                        void operator()( bool bNew, value_type& item, value_type& val );
+                    };
+                \endcode
+                with arguments:
+                - \p bNew - \p true if the item has been inserted, \p false otherwise
+                - \p item - item of the set
+                - \p val - argument \p val passed into the \p %update() function
+                If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
+                refers to the same thing.
+
+                The functor may change non-key fields of the \p item.
+                @warning For \ref cds_intrusive_MichaelList_hp "MichaelList" 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.
+
+            <b>for \p IterableList</b>
+                \code
+                void func( value_type& val, value_type * old );
+                \endcode
+                where
+                - \p val - argument \p val passed into the \p %update() function
+                - \p old - old value that will be retired. If new item has been inserted then \p old is \p nullptr.
 
             Returns <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".
-            \ref cds_intrusive_LazyList_hp "LazyList" provides exclusive access to inserted item and does not require any node-level
-            synchronization.
         */
         template <typename Func>
         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
@@ -496,6 +521,35 @@ namespace cds { namespace intrusive {
         }
         //@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.
+        */
+#ifdef CDS_DOXYGEN_INVOKED
+        std::pair<bool, bool> upsert( value_type& val, bool bAllowInsert = true )
+#else
+        template <typename Q>
+        typename std::enable_if< 
+            std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value,
+            std::pair<bool, bool>
+        >::type
+        upsert( Q& val, bool bAllowInsert = true )
+#endif
+        {
+            std::pair<bool, bool> bRet = bucket( val ).upsert( val, bAllowInsert );
+            if ( bRet.second )
+                ++m_ItemCounter;
+            return bRet;
+        }
+
         /// Unlinks the item \p val from the set
         /**
             The function searches the item \p val in the set and unlink it
@@ -682,6 +736,40 @@ namespace cds { namespace intrusive {
         }
         //@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 )
+        {
+            bucket_type& b = bucket( key );
+            typename ordered_list::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 )
+        {
+            bucket_type& b = bucket( key );
+            typename ordered_list::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_intrusive_MichaelHashSet_hp_find_func "find(Q&, Func)"
@@ -702,6 +790,43 @@ namespace cds { namespace intrusive {
         }
         //@endcond
 
+        /// 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 )
+        {
+            bucket_type& b = bucket( key );
+            typename ordered_list::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 )
+        {
+            bucket_type& b = bucket( key );
+            typename ordered_list::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
         /**
 
@@ -716,14 +841,6 @@ namespace cds { namespace intrusive {
         {
             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
         /**
@@ -736,14 +853,6 @@ namespace cds { namespace intrusive {
         {
             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_intrusive_MichaelHashSet_hp_get
index 1452537..73584fa 100644 (file)
     <Filter Include="Header Files\cds\algo\flat_combining">\r
       <UniqueIdentifier>{fe703227-44ad-4ad6-bae4-b6c9f5c65355}</UniqueIdentifier>\r
     </Filter>\r
-    <Filter Include="Header Files\cds\gc\container">\r
+    <Filter Include="Header Files\cds\container">\r
       <UniqueIdentifier>{84ca9e83-f6c9-4503-a45f-14f08317fd70}</UniqueIdentifier>\r
     </Filter>\r
-    <Filter Include="Header Files\cds\gc\container\details">\r
+    <Filter Include="Header Files\cds\container\details">\r
       <UniqueIdentifier>{4b79fe31-4f6c-4e05-8910-1151a26d51f3}</UniqueIdentifier>\r
     </Filter>\r
-    <Filter Include="Header Files\cds\gc\container\striped_map">\r
+    <Filter Include="Header Files\cds\container\striped_map">\r
       <UniqueIdentifier>{6530b757-5bb7-4de0-b1c9-019acc8183ba}</UniqueIdentifier>\r
     </Filter>\r
-    <Filter Include="Header Files\cds\gc\container\striped_set">\r
+    <Filter Include="Header Files\cds\container\striped_set">\r
       <UniqueIdentifier>{d3f68c37-8c36-448e-9d4c-cd89a940d275}</UniqueIdentifier>\r
     </Filter>\r
-    <Filter Include="Header Files\cds\gc\container\impl">\r
+    <Filter Include="Header Files\cds\container\impl">\r
       <UniqueIdentifier>{0a2328b4-ff6f-4afb-8de0-9884ae172fa9}</UniqueIdentifier>\r
     </Filter>\r
   </ItemGroup>\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\fcdeque.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\fcpriority_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\fcqueue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\fcstack.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_kvlist_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_kvlist_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_list_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_list_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_kvlist_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_kvlist_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_list_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_list_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_map.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_map_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_set.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_set_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\moir_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\msqueue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\optimistic_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\rwqueue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\segmented_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\split_list_map.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\split_list_map_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\split_list_set.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\split_list_set_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\treiber_stack.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\tsigas_cycle_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\vyukov_mpmc_cycle_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\guarded_ptr_cast.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\make_lazy_kvlist.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\make_lazy_list.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\make_michael_kvlist.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\make_michael_list.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\compiler\cxx11_atomic.h">\r
       <Filter>Header Files\cds\compiler</Filter>\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\basket_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\cuckoo_set.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
       <Filter>Header Files\cds\intrusive\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\adapter.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\boost_flat_set.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\boost_list.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\boost_set.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\boost_slist.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\boost_stable_vector.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\boost_unordered_set.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\boost_vector.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\std_hash_set.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\std_list.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\std_set.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set\std_vector.h">\r
-      <Filter>Header Files\cds\gc\container\striped_set</Filter>\r
+      <Filter>Header Files\cds\container\striped_set</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\boost_flat_map.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\boost_list.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\boost_map.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\boost_slist.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\boost_unordered_map.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\std_hash_map.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\std_list.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map\std_map.h">\r
-      <Filter>Header Files\cds\gc\container\striped_map</Filter>\r
+      <Filter>Header Files\cds\container\striped_map</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_map.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\striped_set.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\cuckoo_set.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\cuckoo_map.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\skip_list_hp.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_set_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\make_skip_list_set.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_map_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\make_skip_list_map.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\details\static_functor.h">\r
       <Filter>Header Files\cds\details</Filter>\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_list_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_list_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_kvlist_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_kvlist_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\split_list_rcu.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\split_list_set_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_map_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_set_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\split_list_map_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\skip_list_rcu.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_set_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_map_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\skip_list_nogc.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
       <Filter>Header Files\cds\threading</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_set_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_map_nogc.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\details\binary_functor_wrapper.h">\r
       <Filter>Header Files\cds\details</Filter>\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\ellen_bintree_set_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\memory\pool_allocator.h">\r
       <Filter>Header Files\cds\memory</Filter>\r
       <Filter>Header Files\cds\memory</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\ellen_bintree_map_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\details\bit_reverse_counter.h">\r
       <Filter>Header Files\cds\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\mspriority_queue.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\compiler\icl\compiler_barriers.h">\r
       <Filter>Header Files\cds\compiler\icl</Filter>\r
       <Filter>Header Files\cds\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\ellen_bintree_map_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\ellen_bintree_set_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\mspriority_queue.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
       <Filter>Header Files\cds\lock</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\make_split_list_set.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\compiler\gcc\x86\cxx11_atomic32.h">\r
       <Filter>Header Files\cds\compiler\gcc\x86</Filter>\r
       <Filter>Header Files\cds\intrusive\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\cuckoo_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\ellen_bintree_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\ellen_bintree_map.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\ellen_bintree_set.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\lazy_kvlist.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\lazy_list_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\lazy_list.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\michael_kvlist.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\michael_list_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\michael_list.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\michael_map_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\michael_set_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\skip_list_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\skip_list_map.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\skip_list_set.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\split_list_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_list_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\michael_list_dhp.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\michael_kvlist_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\lazy_list_dhp.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_list_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\lazy_kvlist_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\skip_list_dhp.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_set_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\skip_list_map_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\ellen_bintree_dhp.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\ellen_bintree_map_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\ellen_bintree_set_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\gc\dhp.h">\r
       <Filter>Header Files\cds\gc</Filter>\r
       <Filter>Header Files\cds\algo</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\bronson_avltree_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\bronson_avltree_map_rcu.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\bronson_avltree_map_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\sync\spinlock.h">\r
       <Filter>Header Files\cds\sync</Filter>\r
       <Filter>Header Files\cds\algo</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\feldman_hashset_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\feldman_hashset.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\feldman_hashset_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\feldman_hashset_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\details\feldman_hashmap_base.h">\r
-      <Filter>Header Files\cds\gc\container\details</Filter>\r
+      <Filter>Header Files\cds\container\details</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\impl\feldman_hashmap.h">\r
-      <Filter>Header Files\cds\gc\container\impl</Filter>\r
+      <Filter>Header Files\cds\container\impl</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\feldman_hashmap_dhp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\feldman_hashmap_hp.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\feldman_hashset_rcu.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\feldman_hashset_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\container\feldman_hashmap_rcu.h">\r
-      <Filter>Header Files\cds\gc\container</Filter>\r
+      <Filter>Header Files\cds\container</Filter>\r
     </ClInclude>\r
     <ClInclude Include="..\..\..\cds\intrusive\free_list.h">\r
       <Filter>Header Files\cds\intrusive</Filter>\r
index 72ddedd..603fe7b 100644 (file)
@@ -27,6 +27,8 @@
     </ProjectConfiguration>\r
   </ItemGroup>\r
   <ItemGroup>\r
+    <ClCompile Include="..\..\..\test\unit\intrusive-set\intrusive_michael_iterable_dhp.cpp" />\r
+    <ClCompile Include="..\..\..\test\unit\intrusive-set\intrusive_michael_iterable_hp.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\main.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\intrusive-set\intrusive_feldman_hashset_dhp.cpp" />\r
     <ClCompile Include="..\..\..\test\unit\intrusive-set\intrusive_feldman_hashset_hp.cpp" />\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_feldman_hashset.h" />\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_feldman_hashset_hp.h" />\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_feldman_hashset_rcu.h" />\r
+    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_michael_iterable.h" />\r
+    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_michael_iterable_hp.h" />\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_michael_lazy_rcu.h" />\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_michael_michael_rcu.h" />\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set.h" />\r
index b1946ec..027cb08 100644 (file)
     <ClCompile Include="..\..\..\test\unit\intrusive-set\intrusive_feldman_hashset_rcu_sht.cpp">\r
       <Filter>Source Files\FeldmanHashSet</Filter>\r
     </ClCompile>\r
+    <ClCompile Include="..\..\..\test\unit\intrusive-set\intrusive_michael_iterable_hp.cpp">\r
+      <Filter>Source Files\MichaelSet</Filter>\r
+    </ClCompile>\r
+    <ClCompile Include="..\..\..\test\unit\intrusive-set\intrusive_michael_iterable_dhp.cpp">\r
+      <Filter>Source Files\MichaelSet</Filter>\r
+    </ClCompile>\r
   </ItemGroup>\r
   <ItemGroup>\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_set.h">\r
     <ClInclude Include="..\..\..\test\unit\intrusive-set\test_michael_michael_rcu.h">\r
       <Filter>Header Files</Filter>\r
     </ClInclude>\r
+    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_michael_iterable.h">\r
+      <Filter>Header Files</Filter>\r
+    </ClInclude>\r
+    <ClInclude Include="..\..\..\test\unit\intrusive-set\test_intrusive_michael_iterable_hp.h">\r
+      <Filter>Header Files</Filter>\r
+    </ClInclude>\r
   </ItemGroup>\r
 </Project>
\ No newline at end of file
index a05cce6..f8c0094 100644 (file)
@@ -11,6 +11,8 @@ set(CDSGTEST_SET_SOURCES
     intrusive_feldman_hashset_rcu_gpt.cpp
     intrusive_feldman_hashset_rcu_shb.cpp
     intrusive_feldman_hashset_rcu_sht.cpp
+    intrusive_michael_iterable_dhp.cpp
+    intrusive_michael_iterable_hp.cpp
     intrusive_michael_lazy_hp.cpp
     intrusive_michael_lazy_dhp.cpp
     intrusive_michael_lazy_nogc.cpp
diff --git a/test/unit/intrusive-set/intrusive_michael_iterable_dhp.cpp b/test/unit/intrusive-set/intrusive_michael_iterable_dhp.cpp
new file mode 100644 (file)
index 0000000..6a2b89a
--- /dev/null
@@ -0,0 +1,126 @@
+/*
+    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_intrusive_michael_iterable_hp.h"
+
+#include <cds/intrusive/iterable_list_dhp.h>
+#include <cds/intrusive/michael_set.h>
+
+namespace {
+    namespace ci = cds::intrusive;
+    typedef cds::gc::DHP gc_type;
+
+    class IntrusiveMichaelIterableSet_DHP : public cds_test::intrusive_set_hp
+    {
+    protected:
+        typedef cds_test::intrusive_set_hp base_class;
+
+    protected:
+        void SetUp()
+        {
+            struct list_traits : public ci::iterable_list::traits
+            {};
+            typedef ci::IterableList< gc_type, item_type, list_traits > list_type;
+            typedef ci::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( IntrusiveMichaelIterableSet_DHP, cmp )
+    {
+        typedef ci::IterableList< gc_type
+            , item_type
+            ,ci::iterable_list::make_traits<
+                ci::opt::compare< cmp<item_type> >
+                ,ci::opt::disposer< mock_disposer >
+            >::type
+        > bucket_type;
+
+        typedef ci::MichaelHashSet< gc_type, bucket_type,
+            ci::michael_set::make_traits<
+                ci::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveMichaelIterableSet_DHP, less )
+    {
+        typedef ci::IterableList< gc_type
+            , item_type
+            ,ci::iterable_list::make_traits<
+                ci::opt::less< less<item_type> >
+                ,ci::opt::disposer< mock_disposer >
+            >::type
+        > bucket_type;
+
+        typedef ci::MichaelHashSet< gc_type, bucket_type,
+            ci::michael_set::make_traits<
+                ci::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveMichaelIterableSet_DHP, cmpmix )
+    {
+        struct list_traits : public ci::iterable_list::traits
+        {
+            typedef base_class::less<item_type> less;
+            typedef cmp<item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::IterableList< gc_type, item_type, list_traits > bucket_type;
+
+        struct set_traits : public ci::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+        };
+        typedef ci::MichaelHashSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+} // namespace
diff --git a/test/unit/intrusive-set/intrusive_michael_iterable_hp.cpp b/test/unit/intrusive-set/intrusive_michael_iterable_hp.cpp
new file mode 100644 (file)
index 0000000..4498172
--- /dev/null
@@ -0,0 +1,127 @@
+/*
+    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_intrusive_michael_iterable_hp.h"
+
+#include <cds/intrusive/iterable_list_hp.h>
+#include <cds/intrusive/michael_set.h>
+
+namespace {
+    namespace ci = cds::intrusive;
+    typedef cds::gc::HP gc_type;
+
+    class IntrusiveMichaelIterableSet_HP : public cds_test::intrusive_set_hp
+    {
+    protected:
+        typedef cds_test::intrusive_set_hp base_class;
+
+    protected:
+        void SetUp()
+        {
+            struct list_traits : public ci::iterable_list::traits
+            {};
+            typedef ci::IterableList< gc_type, item_type, list_traits > list_type;
+            typedef ci::MichaelHashSet< gc_type, list_type >   set_type;
+
+            // +3 - for 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( IntrusiveMichaelIterableSet_HP, cmp )
+    {
+        typedef ci::IterableList< gc_type
+            , item_type
+            ,ci::iterable_list::make_traits<
+                ci::opt::compare< cmp<item_type> >
+                ,ci::opt::disposer< mock_disposer >
+            >::type
+        > bucket_type;
+
+        typedef ci::MichaelHashSet< gc_type, bucket_type,
+            ci::michael_set::make_traits<
+                ci::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveMichaelIterableSet_HP, less )
+    {
+        typedef ci::IterableList< gc_type
+            , item_type
+            ,ci::iterable_list::make_traits<
+                ci::opt::less< less<item_type> >
+                ,ci::opt::disposer< mock_disposer >
+            >::type
+        > bucket_type;
+
+        typedef ci::MichaelHashSet< gc_type, bucket_type,
+            ci::michael_set::make_traits<
+                ci::opt::hash< hash_int >
+            >::type
+        > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+    TEST_F( IntrusiveMichaelIterableSet_HP, cmpmix )
+    {
+        struct list_traits : public ci::iterable_list::traits
+        {
+            typedef base_class::less<item_type> less;
+            typedef cmp<item_type> compare;
+            typedef mock_disposer disposer;
+        };
+        typedef ci::IterableList< gc_type, item_type, list_traits > bucket_type;
+
+        struct set_traits : public ci::michael_set::traits
+        {
+            typedef hash_int hash;
+            typedef simple_item_counter item_counter;
+        };
+        typedef ci::MichaelHashSet< gc_type, bucket_type, set_traits > set_type;
+
+        set_type s( kSize, 2 );
+        test( s );
+    }
+
+} // namespace
index 035c21f..f722718 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_intrusive_set_hp.h"
index a97824d..f408b47 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_intrusive_set_hp.h"
diff --git a/test/unit/intrusive-set/test_intrusive_michael_iterable.h b/test/unit/intrusive-set/test_intrusive_michael_iterable.h
new file mode 100644 (file)
index 0000000..e150746
--- /dev/null
@@ -0,0 +1,417 @@
+/*
+    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_INTRUSIVE_MICHAEL_ITERABLE_H
+#define CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_H
+
+#include <cds_test/check_size.h>
+#include <cds_test/fixture.h>
+
+#include <cds/opt/hash.h>
+#include <functional>   // ref
+
+// forward declaration
+namespace cds { namespace intrusive {}}
+
+namespace cds_test {
+
+    namespace ci = cds::intrusive;
+    namespace co = cds::opt;
+
+    class intrusive_set: public fixture
+    {
+    public:
+        static size_t const kSize = 100;
+
+        struct stat
+        {
+            unsigned int nDisposeCount  ;   // count of disposer calling
+            unsigned int nFindCount     ;   // count of find-functor calling
+            unsigned int nUpdateNewCount;
+            unsigned int nUpdateCount;
+            mutable unsigned int nEraseCount;
+
+            stat()
+            {
+                clear_stat();
+            }
+
+            void clear_stat()
+            {
+                memset( this, 0, sizeof( *this ) );
+            }
+        };
+
+        struct item_type: public stat
+        {
+            int nKey;
+            int nVal;
+
+            item_type( int k )
+                : nKey(k)
+                , nVal(0)
+            {}
+
+            int key() const 
+            { 
+                return nKey; 
+            }
+        };
+
+        struct hash_int {
+            size_t operator()( int i ) const
+            {
+                return co::v::hash<int>()( i );
+            }
+            template <typename Q>
+            size_t operator()( Q const& 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;
+            }
+
+        };
+
+
+        template <typename T>
+        struct less
+        {
+            bool operator ()(const T& v1, const T& v2 ) const
+            {
+                return v1.key() < v2.key();
+            }
+
+            template <typename Q>
+            bool operator ()(const T& v1, const Q& v2 ) const
+            {
+                return v1.key() < v2;
+            }
+
+            template <typename Q>
+            bool operator ()(const Q& v1, const T& v2 ) const
+            {
+                return v1 < v2.key();
+            }
+        };
+
+        template <typename T>
+        struct cmp {
+            int operator ()(const T& v1, const T& v2 ) const
+            {
+                if ( v1.key() < v2.key() )
+                    return -1;
+                return v1.key() > v2.key() ? 1 : 0;
+            }
+
+            template <typename Q>
+            int operator ()(const T& v1, const Q& v2 ) const
+            {
+                if ( v1.key() < v2 )
+                    return -1;
+                return v1.key() > v2 ? 1 : 0;
+            }
+
+            template <typename Q>
+            int operator ()(const Q& v1, const T& v2 ) const
+            {
+                if ( v1 < v2.key() )
+                    return -1;
+                return v1 > v2.key() ? 1 : 0;
+            }
+        };
+
+        struct other_item {
+            int nKey;
+
+            explicit other_item( int k )
+                : nKey( k )
+            {}
+
+            int key() const
+            {
+                return nKey;
+            }
+        };
+
+        struct other_less {
+            template <typename Q, typename T>
+            bool operator()( Q const& lhs, T const& rhs ) const
+            {
+                return lhs.key() < rhs.key();
+            }
+        };
+
+        struct mock_disposer
+        {
+            template <typename T>
+            void operator ()( T * p )
+            {
+                ++p->nDisposeCount;
+            }
+        };
+
+    protected:
+        template <class Set>
+        void test( Set& s )
+        {
+            // Precondition: set is empty
+            // Postcondition: set is empty
+
+            ASSERT_TRUE( s.empty() );
+            ASSERT_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 ];
+
+                ASSERT_FALSE( s.contains( i.nKey ));
+                ASSERT_FALSE( s.contains( i ));
+                ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
+                ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
+                ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
+                ASSERT_TRUE( s.find( i.nKey ) == s.end());
+                ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less()) == s.end());
+
+                std::pair<bool, bool> updResult;
+
+                updResult = s.update( i, []( value_type&, value_type* )
+                {
+                    ASSERT_TRUE( false );
+                }, false );
+                EXPECT_FALSE( updResult.first );
+                EXPECT_FALSE( updResult.second );
+
+                updResult = s.upsert( i, false );
+                EXPECT_FALSE( updResult.first );
+                EXPECT_FALSE( updResult.second );
+
+                switch ( i.key() % 4 ) {
+                case 0:
+                    ASSERT_TRUE( s.insert( i ));
+                    ASSERT_FALSE( s.insert( i ));
+                    updResult = s.update( i, []( value_type& val, value_type* arg) 
+                        {
+                            ASSERT_TRUE( arg != nullptr );
+                            EXPECT_EQ( val.key(), arg->key() );
+                        }, false );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_FALSE( updResult.second );
+                    break;
+                case 1:
+                    EXPECT_EQ( i.nUpdateNewCount, 0 );
+                    ASSERT_TRUE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ));
+                    EXPECT_EQ( i.nUpdateNewCount, 1 );
+                    ASSERT_FALSE( s.insert( i, []( value_type& v ) { ++v.nUpdateNewCount;} ) );
+                    EXPECT_EQ( i.nUpdateNewCount, 1 );
+                    i.nUpdateNewCount = 0;
+                    break;
+                case 2:
+                    updResult = s.update( i, []( value_type& /*val*/, value_type* arg )
+                    {
+                        EXPECT_TRUE( arg == nullptr );
+                    });
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_TRUE( updResult.second );
+                    break;
+                case 3:
+                    updResult = s.upsert( i );
+                    EXPECT_TRUE( updResult.first );
+                    EXPECT_TRUE( updResult.second );
+                    break;
+                }
+
+                ASSERT_TRUE( s.contains( i.nKey ) );
+                ASSERT_TRUE( s.contains( i ) );
+                ASSERT_TRUE( s.contains( other_item( i.key() ), other_less()));
+                EXPECT_EQ( i.nFindCount, 0 );
+                ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ));
+                EXPECT_EQ( i.nFindCount, 1 );
+                ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ));
+                EXPECT_EQ( i.nFindCount, 2 );
+                ASSERT_TRUE( s.find( i.nKey ) != s.end() );
+                ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less() ) != s.end() );
+                EXPECT_EQ( s.find( i.nKey )->nKey, i.key() );
+                EXPECT_EQ( s.find_with( other_item( i.key() ), other_less())->nKey, i.key() );
+            }
+            ASSERT_FALSE( s.empty() );
+            ASSERT_CONTAINER_SIZE( s, nSetSize );
+
+            std::for_each( data.begin(), data.end(), []( value_type& v ) { v.clear_stat(); });
+
+            // erase
+            shuffle( indices.begin(), indices.end() );
+            for ( auto idx : indices ) {
+                auto& i = data[ idx ];
+
+                ASSERT_TRUE( s.contains( i.nKey ) );
+                ASSERT_TRUE( s.contains( i ) );
+                ASSERT_TRUE( s.contains( other_item( i.key() ), other_less() ) );
+                EXPECT_EQ( i.nFindCount, 0 );
+                ASSERT_TRUE( s.find( i.nKey, []( value_type& v, int ) { ++v.nFindCount; } ) );
+                EXPECT_EQ( i.nFindCount, 1 );
+                ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less(), []( value_type& v, other_item const& ) { ++v.nFindCount; } ) );
+                EXPECT_EQ( i.nFindCount, 2 );
+                ASSERT_TRUE( s.find( i.nKey ) != s.end() );
+                ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less()) != s.end() );
+                EXPECT_EQ( s.find( i.nKey )->nKey, i.key() );
+                EXPECT_EQ( s.find_with( other_item( i.key() ), other_less())->nKey, i.key() );
+
+
+                value_type v( i );
+                switch ( i.key() % 6 ) {
+                case 0:
+                    ASSERT_FALSE( s.unlink( v ));
+                    ASSERT_TRUE( s.unlink( i ));
+                    ASSERT_FALSE( s.unlink( i ) );
+                    break;
+                case 1:
+                    ASSERT_TRUE( s.erase( i.key()));
+                    ASSERT_FALSE( s.erase( i.key() ) );
+                    break;
+                case 2:
+                    ASSERT_TRUE( s.erase( v ));
+                    ASSERT_FALSE( s.erase( v ) );
+                    break;
+                case 3:
+                    ASSERT_TRUE( s.erase_with( other_item( i.key()), other_less()));
+                    ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less() ) );
+                    break;
+                case 4:
+                    EXPECT_EQ( i.nEraseCount, 0 );
+                    ASSERT_TRUE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
+                    EXPECT_EQ( i.nEraseCount, 1 );
+                    ASSERT_FALSE( s.erase( v, []( value_type& val ) { ++val.nEraseCount; } ));
+                    EXPECT_EQ( i.nEraseCount, 1 );
+                    break;
+                case 5:
+                    EXPECT_EQ( i.nEraseCount, 0 );
+                    ASSERT_TRUE( s.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
+                    EXPECT_EQ( i.nEraseCount, 1 );
+                    ASSERT_FALSE( s.erase_with( other_item( i.key() ), other_less(), []( value_type& val ) { ++val.nEraseCount; } ));
+                    EXPECT_EQ( i.nEraseCount, 1 );
+                    break;
+                }
+
+                ASSERT_FALSE( s.contains( i.nKey ));
+                ASSERT_FALSE( s.contains( i ));
+                ASSERT_FALSE( s.contains( other_item( i.key()), other_less()));
+                ASSERT_FALSE( s.find( i.nKey, []( value_type&, int ) {} ));
+                ASSERT_FALSE( s.find_with( other_item( i.key()), other_less(), []( value_type&, other_item const& ) {} ));
+                ASSERT_TRUE( s.find( i.nKey ) == s.end() );
+                ASSERT_TRUE( s.find_with( other_item( i.key() ), other_less() ) == s.end() );
+            }
+            ASSERT_TRUE( s.empty() );
+            ASSERT_CONTAINER_SIZE( s, 0 );
+
+            // Force retiring cycle
+            Set::gc::force_dispose();
+            for ( auto& i : data ) {
+                EXPECT_EQ( i.nDisposeCount, 1 );
+            }
+
+            // clear
+            for ( auto& i : data ) {
+                i.clear_stat();
+                ASSERT_TRUE( s.insert( i ));
+            }
+            ASSERT_FALSE( s.empty() );
+            ASSERT_CONTAINER_SIZE( s, nSetSize );
+
+            // Iterator test
+            for ( auto it = s.begin(); it != s.end(); ++it ) {
+                ++it->nFindCount;
+            }
+            for ( auto it = s.cbegin(); it != s.cend(); ++it ) {
+                EXPECT_EQ( it->nFindCount, 1 );
+            }
+            for ( auto& i : data ) {
+                EXPECT_EQ( i.nFindCount, 1 );
+            }
+
+            // clear test
+            s.clear();
+
+            ASSERT_TRUE( s.empty());
+            ASSERT_CONTAINER_SIZE( s, 0 );
+            ASSERT_TRUE( s.begin() == s.end() );
+            ASSERT_TRUE( s.cbegin() == s.cend() );
+
+            // Force retiring cycle
+            Set::gc::force_dispose();
+            for ( auto& i : data ) {
+                EXPECT_EQ( i.nDisposeCount, 1 );
+            }
+
+        }
+    };
+
+} // namespace cds_test
+
+#endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_H
diff --git a/test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h b/test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h
new file mode 100644 (file)
index 0000000..65621cf
--- /dev/null
@@ -0,0 +1,160 @@
+/*
+    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_INTRUSIVE_MICHAEL_ITERABLE_HP_H
+#define CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_HP_H
+
+#include "test_intrusive_michael_iterable.h"
+
+// forward declaration
+namespace cds { namespace intrusive {}}
+
+namespace cds_test {
+
+    namespace ci = cds::intrusive;
+    namespace co = cds::opt;
+
+    class intrusive_set_hp: public intrusive_set
+    {
+        typedef intrusive_set base_class;
+
+    protected:
+
+        template <class Set>
+        void test( Set& s )
+        {
+            // Precondition: set is empty
+            // Postcondition: set is empty
+
+            base_class::test( s );
+
+            ASSERT_TRUE( s.empty() );
+            ASSERT_CONTAINER_SIZE( s, 0 );
+
+            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() );
+
+            typename Set::guarded_ptr gp;
+
+            // get/extract from empty set
+            for ( auto idx : indices ) {
+                auto& i = data[idx];
+
+                gp = s.get( i );
+                ASSERT_TRUE( !gp );
+                gp = s.get( i.key() );
+                ASSERT_TRUE( !gp );
+                gp = s.get_with( other_item( i.key()), other_less());
+                ASSERT_TRUE( !gp );
+
+                gp = s.extract( i );
+                ASSERT_TRUE( !gp );
+                gp = s.extract( i.key());
+                ASSERT_TRUE( !gp );
+                gp = s.extract_with( other_item( i.key()), other_less());
+                ASSERT_TRUE( !gp );
+            }
+
+            // fill set
+            for ( auto& i : data ) {
+                i.nDisposeCount = 0;
+                ASSERT_TRUE( s.insert( i ) );
+            }
+
+            // get/extract
+            for ( auto idx : indices ) {
+                auto& i = data[idx];
+
+                EXPECT_EQ( i.nFindCount, 0 );
+                gp = s.get( i );
+                ASSERT_FALSE( !gp );
+                ++gp->nFindCount;
+                EXPECT_EQ( i.nFindCount, 1 );
+
+                gp = s.get( i.key() );
+                ASSERT_FALSE( !gp );
+                ++gp->nFindCount;
+                EXPECT_EQ( i.nFindCount, 2 );
+
+                gp = s.get_with( other_item( i.key()), other_less());
+                ASSERT_FALSE( !gp );
+                ++gp->nFindCount;
+                EXPECT_EQ( i.nFindCount, 3 );
+
+                EXPECT_EQ( i.nEraseCount, 0 );
+                switch ( i.key() % 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;
+                }
+                ASSERT_FALSE( !gp );
+                ++gp->nEraseCount;
+                EXPECT_EQ( i.nEraseCount, 1 );
+
+                gp = s.extract( i );
+                ASSERT_TRUE( !gp );
+                gp = s.extract( i.key() );
+                ASSERT_TRUE( !gp );
+                gp = s.extract_with( other_item( i.key() ), other_less() );
+                ASSERT_TRUE( !gp );
+            }
+
+            gp.release();
+
+            ASSERT_TRUE( s.empty() );
+            ASSERT_CONTAINER_SIZE( s, 0 );
+
+            // Force retiring cycle
+            Set::gc::force_dispose();
+            for ( auto& i : data ) {
+                EXPECT_EQ( i.nDisposeCount, 1 );
+            }
+
+        }
+    };
+
+} // namespace cds_test
+
+#endif // #ifndef CDSUNIT_SET_TEST_INTRUSIVE_MICHAEL_ITERABLE_HP_H
index d6de7f0..f828c3b 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_intrusive_list_hp.h"
@@ -145,6 +145,40 @@ namespace {
         test_ordered_iterator( l );
         test_hp( l );
     }
+    TEST_F( IntrusiveMichaelList_DHP, base_hook_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< base_item > compare;
+            typedef intrusive_list_common::less< base_item > less;
+            typedef cds::intrusive::michael_list::stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, base_item, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( IntrusiveMichaelList_DHP, base_hook_wrapped_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< base_item > compare;
+            typedef cds::intrusive::michael_list::wrapped_stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, base_item, traits > list_type;
+
+        cds::intrusive::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
 
     TEST_F( IntrusiveMichaelList_DHP, member_hook )
     {
@@ -231,4 +265,38 @@ namespace {
         test_hp( l );
     }
 
+    TEST_F( IntrusiveMichaelList_DHP, member_hook_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< member_item > compare;
+            typedef intrusive_list_common::less< member_item > less;
+            typedef cds::intrusive::michael_list::stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, member_item, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( IntrusiveMichaelList_DHP, member_hook_wrapped_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< member_item > compare;
+            typedef cds::intrusive::michael_list::wrapped_stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, member_item, traits > list_type;
+
+        cds::intrusive::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
 } // namespace
index 26b0bb5..693a0bf 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_intrusive_list_hp.h"
@@ -147,6 +147,40 @@ namespace {
         test_hp( l );
     }
 
+    TEST_F( IntrusiveMichaelList_HP, base_hook_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< base_item > compare;
+            typedef intrusive_list_common::less< base_item > less;
+            typedef cds::intrusive::michael_list::stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, base_item, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( IntrusiveMichaelList_HP, base_hook_wrapped_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::base_hook< cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< base_item > compare;
+            typedef cds::intrusive::michael_list::wrapped_stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, base_item, traits > list_type;
+
+        cds::intrusive::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
     TEST_F( IntrusiveMichaelList_HP, member_hook )
     {
         typedef ci::MichaelList< gc_type, member_item,
@@ -232,4 +266,38 @@ namespace {
         test_hp( l );
     }
 
+    TEST_F( IntrusiveMichaelList_HP, member_hook_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< member_item > compare;
+            typedef intrusive_list_common::less< member_item > less;
+            typedef cds::intrusive::michael_list::stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, member_item, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( IntrusiveMichaelList_HP, member_hook_wrapped_stat )
+    {
+        struct traits: public ci::michael_list::traits {
+            typedef ci::michael_list::member_hook< offsetof( member_item, hMember ), cds::opt::gc< gc_type >> hook;
+            typedef mock_disposer disposer;
+            typedef cmp< member_item > compare;
+            typedef cds::intrusive::michael_list::wrapped_stat<> stat;
+        };
+        typedef ci::MichaelList< gc_type, member_item, traits > list_type;
+
+        cds::intrusive::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
 } // namespace
index f942b96..ee2e490 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_kv_list_hp.h"
@@ -143,4 +143,37 @@ namespace {
         test_hp( l );
     }
 
+    TEST_F( MichaelKVList_DHP, stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::stat<> stat;
+        };
+        typedef cc::MichaelKVList<gc_type, key_type, value_type, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( MichaelKVList_DHP, wrapped_stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::wrapped_stat<> stat;
+        };
+        typedef cc::MichaelKVList<gc_type, key_type, value_type, traits > list_type;
+
+        cds::container::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
 } // namespace
index baca4a3..2912dcc 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_kv_list_hp.h"
@@ -144,4 +144,37 @@ namespace {
         test_hp( l );
     }
 
+    TEST_F( MichaelKVList_HP, stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::stat<> stat;
+        };
+        typedef cc::MichaelKVList<gc_type, key_type, value_type, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( MichaelKVList_HP, wrapped_stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::wrapped_stat<> stat;
+        };
+        typedef cc::MichaelKVList<gc_type, key_type, value_type, traits > list_type;
+
+        cds::container::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
 } // namespace
index 083aa6d..6f81d5f 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_kv_list_nogc.h"
@@ -122,4 +122,35 @@ namespace {
         test_ordered_iterator( l );
     }
 
+    TEST_F( MichaelKVList_NOGC, stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::stat<> stat;
+        };
+        typedef cc::MichaelKVList<gc_type, key_type, value_type, traits > list_type;
+
+        list_type l;
+        test( l );
+        test_ordered_iterator( l );
+    }
+
+    TEST_F( MichaelKVList_NOGC, wrapped_stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::wrapped_stat<> stat;
+        };
+        typedef cc::MichaelKVList<gc_type, key_type, value_type, traits > list_type;
+
+        cds::container::michael_list::stat<> st;
+        list_type l( st );
+        test( l );
+        test_ordered_iterator( l );
+    }
+
 } // namespace
index 1ecabe2..65450e9 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_list_hp.h"
@@ -143,4 +143,39 @@ namespace {
         test_hp( l );
     }
 
+    TEST_F( MichaelList_DHP, stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt<item> less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::stat<> stat;
+
+        };
+        typedef cc::MichaelList<gc_type, item, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( MichaelList_DHP, wrapped_stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt<item> less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::wrapped_stat<> stat;
+
+        };
+        typedef cc::MichaelList<gc_type, item, traits > list_type;
+
+        cds::container::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
 } // namespace
index 6a2261b..bb28f46 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_list_hp.h"
@@ -144,4 +144,39 @@ namespace {
         test_hp( l );
     }
 
+    TEST_F( MichaelList_HP, stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt<item> less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::stat<> stat;
+
+        };
+        typedef cc::MichaelList<gc_type, item, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( MichaelList_HP, wrapped_stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt<item> less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::wrapped_stat<> stat;
+
+        };
+        typedef cc::MichaelList<gc_type, item, traits > list_type;
+
+        cds::container::michael_list::stat<> st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
 } // namespace
index 88331cb..4ad27ce 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_list_nogc.h"
@@ -122,4 +122,35 @@ namespace {
         test_ordered_iterator( l );
     }
 
+    TEST_F( MichaelList_NOGC, stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt<item> less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::stat<> stat;
+        };
+        typedef cc::MichaelList<gc_type, item, traits > list_type;
+
+        list_type l;
+        test( l );
+        test_ordered_iterator( l );
+    }
+
+    TEST_F( MichaelList_NOGC, wrapped_stat )
+    {
+        struct traits: public cc::michael_list::traits
+        {
+            typedef lt<item> less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::container::michael_list::wrapped_stat<> stat;
+        };
+        typedef cc::MichaelList<gc_type, item, traits > list_type;
+
+        cds::container::michael_list::stat<> st;
+        list_type l{ st };
+        test( l );
+        test_ordered_iterator( l );
+    }
+
 } // namespace
index 3bdfaa6..8416a4c 100644 (file)
@@ -278,11 +278,11 @@ namespace cds_test {
                     break;
                 case 3:
                     {
-                        std::pair<bool, bool> ret = l.update( i, false );
+                        std::pair<bool, bool> ret = l.upsert( i, false );
                         EXPECT_EQ( ret.first, false );
                         EXPECT_EQ( ret.second, false );
 
-                        ret = l.update( i );
+                        ret = l.upsert( i );
                         EXPECT_EQ( ret.first, true );
                         EXPECT_EQ( ret.second, true );
                     }
index 45b0b2a..6592468 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 CDSUNIT_LIST_TEST_INTRUSIVE_MICHAEL_LIST_RCU_H
 #define CDSUNIT_LIST_TEST_INTRUSIVE_MICHAEL_LIST_RCU_H
@@ -144,6 +144,39 @@ TYPED_TEST_P( IntrusiveMichaelList, base_hook_seqcst )
     this->test_rcu( l );
 }
 
+TYPED_TEST_P( IntrusiveMichaelList, base_hook_stat )
+{
+    struct traits: public ci::michael_list::traits {
+        typedef ci::michael_list::base_hook< cds::opt::gc< typename TestFixture::rcu_type >> hook;
+        typedef typename TestFixture::mock_disposer disposer;
+        typedef typename TestFixture::template cmp< typename TestFixture::base_item > compare;
+        typedef cds::intrusive::michael_list::stat<> stat;
+    };
+    typedef ci::MichaelList< typename TestFixture::rcu_type, typename TestFixture::base_item, traits > list_type;
+
+    list_type l;
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
+TYPED_TEST_P( IntrusiveMichaelList, base_hook_wrapped_stat )
+{
+    struct traits: public ci::michael_list::traits {
+        typedef ci::michael_list::base_hook< cds::opt::gc< typename TestFixture::rcu_type >> hook;
+        typedef typename TestFixture::mock_disposer disposer;
+        typedef typename TestFixture::template cmp< typename TestFixture::base_item > compare;
+        typedef cds::intrusive::michael_list::wrapped_stat<> stat;
+    };
+    typedef ci::MichaelList< typename TestFixture::rcu_type, typename TestFixture::base_item, traits > list_type;
+
+    cds::intrusive::michael_list::stat<> st;
+    list_type l( st );
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
 TYPED_TEST_P( IntrusiveMichaelList, member_hook )
 {
     typedef ci::MichaelList< typename TestFixture::rcu_type, typename TestFixture::member_item,
@@ -228,11 +261,44 @@ TYPED_TEST_P( IntrusiveMichaelList, member_hook_back_off )
     this->test_rcu( l );
 }
 
+TYPED_TEST_P( IntrusiveMichaelList, member_hook_stat )
+{
+    struct traits: public ci::michael_list::traits {
+        typedef ci::michael_list::member_hook< offsetof( typename TestFixture::member_item, hMember ), cds::opt::gc< typename TestFixture::rcu_type >> hook;
+        typedef typename TestFixture::mock_disposer disposer;
+        typedef typename TestFixture::template cmp< typename TestFixture::member_item > compare;
+        typedef cds::intrusive::michael_list::stat<> stat;
+    };
+    typedef ci::MichaelList< typename TestFixture::rcu_type, typename TestFixture::member_item, traits > list_type;
+
+    list_type l;
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
+TYPED_TEST_P( IntrusiveMichaelList, member_hook_wrapped_stat )
+{
+    struct traits: public ci::michael_list::traits {
+        typedef ci::michael_list::member_hook< offsetof( typename TestFixture::member_item, hMember ), cds::opt::gc< typename TestFixture::rcu_type >> hook;
+        typedef typename TestFixture::mock_disposer disposer;
+        typedef typename TestFixture::template cmp< typename TestFixture::member_item > compare;
+        typedef cds::intrusive::michael_list::wrapped_stat<> stat;
+    };
+    typedef ci::MichaelList< typename TestFixture::rcu_type, typename TestFixture::member_item, traits > list_type;
+
+    cds::intrusive::michael_list::stat<> st;
+    list_type l( st );
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
 
 // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
 // "No test named <test_name> can be found in this test case"
 REGISTER_TYPED_TEST_CASE_P( IntrusiveMichaelList,
-    base_hook, base_hook_cmp, base_hook_item_counting, base_hook_backoff, base_hook_seqcst, member_hook, member_hook_cmp, member_hook_item_counting, member_hook_seqcst, member_hook_back_off
+    base_hook, base_hook_cmp, base_hook_item_counting, base_hook_backoff, base_hook_seqcst, base_hook_stat, base_hook_wrapped_stat, member_hook, member_hook_cmp, member_hook_item_counting, member_hook_seqcst, member_hook_back_off, member_hook_stat, member_hook_wrapped_stat
 );
 
 
index 730049b..54a8239 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 CDSUNIT_LIST_TEST_MICHAEL_KV_LIST_RCU_H
 #define CDSUNIT_LIST_TEST_MICHAEL_KV_LIST_RCU_H
@@ -148,10 +148,43 @@ TYPED_TEST_P( MichaelKVList, seq_cst )
     this->test_rcu( l );
 }
 
+TYPED_TEST_P( MichaelKVList, stat )
+{
+    struct traits: public cc::michael_list::traits
+    {
+        typedef typename TestFixture::lt less;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::container::michael_list::stat<> stat;
+    };
+    typedef cc::MichaelKVList<typename TestFixture::rcu_type, typename TestFixture::key_type, typename TestFixture::value_type, traits > list_type;
+
+    list_type l;
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
+TYPED_TEST_P( MichaelKVList, wrapped_stat )
+{
+    struct traits: public cc::michael_list::traits
+    {
+        typedef typename TestFixture::lt less;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::container::michael_list::wrapped_stat<> stat;
+    };
+    typedef cc::MichaelKVList<typename TestFixture::rcu_type, typename TestFixture::key_type, typename TestFixture::value_type, traits > list_type;
+
+    cds::container::michael_list::stat<> st;
+    list_type l( st );
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
 // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
 // "No test named <test_name> can be found in this test case"
 REGISTER_TYPED_TEST_CASE_P( MichaelKVList,
-    less_ordered, compare_ordered, mix_ordered, item_counting, backoff, seq_cst
+    less_ordered, compare_ordered, mix_ordered, item_counting, backoff, seq_cst, stat, wrapped_stat
     );
 
 #endif // CDSUNIT_LIST_TEST_MICHAEL_KV_LIST_RCU_H
index 143afc4..f0e4059 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 CDSUNIT_LIST_TEST_MICHAEL_LIST_RCU_H
 #define CDSUNIT_LIST_TEST_MICHAEL_LIST_RCU_H
@@ -148,10 +148,43 @@ TYPED_TEST_P( MichaelList, seq_cst )
     this->test_rcu( l );
 }
 
+TYPED_TEST_P( MichaelList, stat )
+{
+    struct traits: public cc::michael_list::traits
+    {
+        typedef typename TestFixture::template lt< typename TestFixture::item> less;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::container::michael_list::stat<> stat;
+    };
+    typedef cc::MichaelList<typename TestFixture::rcu_type, typename TestFixture::item, traits > list_type;
+
+    list_type l;
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
+TYPED_TEST_P( MichaelList, wrapped_stat )
+{
+    struct traits: public cc::michael_list::traits
+    {
+        typedef typename TestFixture::template lt< typename TestFixture::item> less;
+        typedef cds::atomicity::item_counter item_counter;
+        typedef cds::container::michael_list::wrapped_stat<> stat;
+    };
+    typedef cc::MichaelList<typename TestFixture::rcu_type, typename TestFixture::item, traits > list_type;
+
+    cds::container::michael_list::stat<> st;
+    list_type l( st );
+    this->test_common( l );
+    this->test_ordered_iterator( l );
+    this->test_rcu( l );
+}
+
 // GCC 5: All test names should be written on single line, otherwise a runtime error will be encountered like as
 // "No test named <test_name> can be found in this test case"
 REGISTER_TYPED_TEST_CASE_P( MichaelList,
-    less_ordered, compare_ordered, mix_ordered, item_counting, backoff, seq_cst
+    less_ordered, compare_ordered, mix_ordered, item_counting, backoff, seq_cst, stat, wrapped_stat
     );
 
 #endif // CDSUNIT_LIST_TEST_MICHAEL_LIST_RCU_H