From 81228560a25c8db60150a3df112271fd40d161f3 Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 25 Jul 2016 08:53:36 +0300 Subject: [PATCH] Added internal statistics to MichaelList, IterableList --- cds/container/details/make_michael_kvlist.h | 2 +- cds/container/details/make_michael_list.h | 2 +- cds/container/details/michael_list_base.h | 38 +- cds/container/impl/michael_kvlist.h | 18 +- cds/container/impl/michael_list.h | 16 +- cds/container/michael_kvlist_nogc.h | 18 +- cds/container/michael_kvlist_rcu.h | 18 +- cds/container/michael_list_nogc.h | 18 +- cds/container/michael_list_rcu.h | 16 +- cds/intrusive/details/iterable_list_base.h | 15 + cds/intrusive/details/michael_list_base.h | 106 ++++- cds/intrusive/details/michael_set_base.h | 2 +- cds/intrusive/impl/iterable_list.h | 12 +- cds/intrusive/impl/michael_list.h | 83 +++- cds/intrusive/michael_list_nogc.h | 58 ++- cds/intrusive/michael_list_rcu.h | 94 +++- cds/intrusive/michael_set.h | 199 +++++++-- projects/Win/vc14/cds.vcxproj.filters | 246 +++++------ projects/Win/vc14/gtest-intrusive-set.vcxproj | 4 + .../vc14/gtest-intrusive-set.vcxproj.filters | 12 + test/unit/intrusive-set/CMakeLists.txt | 2 + .../intrusive_michael_iterable_dhp.cpp | 126 ++++++ .../intrusive_michael_iterable_hp.cpp | 127 ++++++ .../intrusive_michael_michael_dhp.cpp | 2 +- .../intrusive_michael_michael_hp.cpp | 2 +- .../test_intrusive_michael_iterable.h | 417 ++++++++++++++++++ .../test_intrusive_michael_iterable_hp.h | 160 +++++++ test/unit/list/intrusive_michael_dhp.cpp | 70 ++- test/unit/list/intrusive_michael_hp.cpp | 70 ++- test/unit/list/kv_michael_dhp.cpp | 35 +- test/unit/list/kv_michael_hp.cpp | 35 +- test/unit/list/kv_michael_nogc.cpp | 33 +- test/unit/list/michael_dhp.cpp | 37 +- test/unit/list/michael_hp.cpp | 37 +- test/unit/list/michael_nogc.cpp | 33 +- test/unit/list/test_intrusive_iterable_list.h | 4 +- test/unit/list/test_intrusive_michael_rcu.h | 70 ++- test/unit/list/test_kv_michael_rcu.h | 37 +- test/unit/list/test_michael_rcu.h | 37 +- 39 files changed, 2061 insertions(+), 250 deletions(-) create mode 100644 test/unit/intrusive-set/intrusive_michael_iterable_dhp.cpp create mode 100644 test/unit/intrusive-set/intrusive_michael_iterable_hp.cpp create mode 100644 test/unit/intrusive-set/test_intrusive_michael_iterable.h create mode 100644 test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h diff --git a/cds/container/details/make_michael_kvlist.h b/cds/container/details/make_michael_kvlist.h index b1513061..385a2c93 100644 --- a/cds/container/details/make_michael_kvlist.h +++ b/cds/container/details/make_michael_kvlist.h @@ -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 diff --git a/cds/container/details/make_michael_list.h b/cds/container/details/make_michael_list.h index 20fea0dc..e779c607 100644 --- a/cds/container/details/make_michael_list.h +++ b/cds/container/details/make_michael_list.h @@ -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 diff --git a/cds/container/details/michael_list_base.h b/cds/container/details/michael_list_base.h index 7169c353..2a64ba44 100644 --- a/cds/container/details/michael_list_base.h +++ b/cds/container/details/michael_list_base.h @@ -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 + 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 > + 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. + - \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 struct make_traits { diff --git a/cds/container/impl/michael_kvlist.h b/cds/container/impl/michael_kvlist.h index 28f18ef6..37f7a499 100644 --- a/cds/container/impl/michael_kvlist.h +++ b/cds/container/impl/michael_kvlist.h @@ -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 >::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 ) diff --git a/cds/container/impl/michael_list.h b/cds/container/impl/michael_list.h index 514dbfd8..27c87b90 100644 --- a/cds/container/impl/michael_list.h +++ b/cds/container/impl/michael_list.h @@ -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 >::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 ) diff --git a/cds/container/michael_kvlist_nogc.h b/cds/container/michael_kvlist_nogc.h index 53f71b0b..89974bf5 100644 --- a/cds/container/michael_kvlist_nogc.h +++ b/cds/container/michael_kvlist_nogc.h @@ -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 >::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() { diff --git a/cds/container/michael_kvlist_rcu.h b/cds/container/michael_kvlist_rcu.h index 175cc234..2dbe9ffe 100644 --- a/cds/container/michael_kvlist_rcu.h +++ b/cds/container/michael_kvlist_rcu.h @@ -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 >::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 diff --git a/cds/container/michael_list_nogc.h b/cds/container/michael_list_nogc.h index b7fbbf6e..1bf897c7 100644 --- a/cds/container/michael_list_nogc.h +++ b/cds/container/michael_list_nogc.h @@ -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 >::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() { diff --git a/cds/container/michael_list_rcu.h b/cds/container/michael_list_rcu.h index 61d16235..861da797 100644 --- a/cds/container/michael_list_rcu.h +++ b/cds/container/michael_list_rcu.h @@ -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 >::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() { diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h index 7ef00bdc..824d2398 100644 --- a/cds/intrusive/details/iterable_list_base.h +++ b/cds/intrusive/details/iterable_list_base.h @@ -245,6 +245,21 @@ namespace cds { namespace intrusive { class IterableList; //@endcond + //@cond + template + struct is_iterable_list { + enum { + value = false + }; + }; + + template + struct is_iterable_list< IterableList< GC, T, Traits >> { + enum { + value = true + }; + }; + //@endcond }} // namespace cds::intrusive diff --git a/cds/intrusive/details/michael_list_base.h b/cds/intrusive/details/michael_list_base.h index 2b72b262..b6cc2caf 100644 --- a/cds/intrusive/details/michael_list_base.h +++ b/cds/intrusive/details/michael_list_base.h @@ -196,6 +196,101 @@ namespace cds { namespace intrusive { //@endcond }; + + /// \p MichaelList internal statistics + template + 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 > + 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" diff --git a/cds/intrusive/details/michael_set_base.h b/cds/intrusive/details/michael_set_base.h index 2e7eef9b..64c08d2d 100644 --- a/cds/intrusive/details/michael_set_base.h +++ b/cds/intrusive/details/michael_set_base.h @@ -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 diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index 00e20233..21f3d5fe 100644 --- a/cds/intrusive/impl/iterable_list.h +++ b/cds/intrusive/impl/iterable_list.h @@ -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 update( value_type& val, bool bInsert = true ) + std::pair 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 diff --git a/cds/intrusive/impl/michael_list.h b/cds/intrusive/impl/michael_list.h index 55c778e0..97bf868d 100644 --- a/cds/intrusive/impl/michael_list.h +++ b/cds/intrusive/impl/michael_list.h @@ -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 >::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( 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 @@ -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( 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; } } diff --git a/cds/intrusive/michael_list_nogc.h b/cds/intrusive/michael_list_nogc.h index 3e3920ba..e7378a79 100644 --- a/cds/intrusive/michael_list_nogc.h +++ b/cds/intrusive/michael_list_nogc.h @@ -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 #include - 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 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 >::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(); } diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index 2b9ae89a..52674262 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -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 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 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 >::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 @@ -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 diff --git a/cds/intrusive/michael_set.h b/cds/intrusive/michael_set.h index b876b5ed..327f09ab 100644 --- a/cds/intrusive/michael_set.h +++ b/cds/intrusive/michael_set.h @@ -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 #include +#include 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: + + for \p MichaelList, \p LazyList + \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. + + for \p IterableList + \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 std::pair 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 std::pair 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 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 upsert( value_type& val, bool bAllowInsert = true ) +#else + template + typename std::enable_if< + std::is_same< Q, value_type>::value && is_iterable_list< ordered_list >::value, + std::pair + >::type + upsert( Q& val, bool bAllowInsert = true ) +#endif + { + std::pair 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 +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::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 std::enable_if< std::is_same::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 +#ifdef CDS_DOXYGEN_INVOKED + iterator +#else + typename std::enable_if< std::is_same::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 std::enable_if< std::is_same::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 - 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 - 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 diff --git a/projects/Win/vc14/cds.vcxproj.filters b/projects/Win/vc14/cds.vcxproj.filters index 14525378..73584fa3 100644 --- a/projects/Win/vc14/cds.vcxproj.filters +++ b/projects/Win/vc14/cds.vcxproj.filters @@ -142,19 +142,19 @@ {fe703227-44ad-4ad6-bae4-b6c9f5c65355} - + {84ca9e83-f6c9-4503-a45f-14f08317fd70} - + {4b79fe31-4f6c-4e05-8910-1151a26d51f3} - + {6530b757-5bb7-4de0-b1c9-019acc8183ba} - + {d3f68c37-8c36-448e-9d4c-cd89a940d275} - + {0a2328b4-ff6f-4afb-8de0-9884ae172fa9} @@ -516,103 +516,103 @@ Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details Header Files\cds\compiler @@ -645,7 +645,7 @@ Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive @@ -687,91 +687,91 @@ Header Files\cds\intrusive\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_set + Header Files\cds\container\striped_set - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container\striped_map + Header Files\cds\container\striped_map - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container\details + Header Files\cds\container\details Header Files\cds\details @@ -825,40 +825,40 @@ Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive @@ -870,10 +870,10 @@ Header Files\cds\threading - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\details @@ -909,7 +909,7 @@ Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\memory @@ -918,13 +918,13 @@ Header Files\cds\memory - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\details - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\compiler\icl @@ -936,10 +936,10 @@ Header Files\cds\details - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive @@ -987,7 +987,7 @@ Header Files\cds\lock - Header Files\cds\gc\container\details + Header Files\cds\container\details Header Files\cds\compiler\gcc\x86 @@ -1029,91 +1029,91 @@ Header Files\cds\intrusive\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\gc @@ -1149,13 +1149,13 @@ Header Files\cds\algo - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\sync @@ -1197,37 +1197,37 @@ Header Files\cds\algo - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container\details + Header Files\cds\container\details - Header Files\cds\gc\container\impl + Header Files\cds\container\impl - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive - Header Files\cds\gc\container + Header Files\cds\container - Header Files\cds\gc\container + Header Files\cds\container Header Files\cds\intrusive diff --git a/projects/Win/vc14/gtest-intrusive-set.vcxproj b/projects/Win/vc14/gtest-intrusive-set.vcxproj index 72ddedd1..603fe7b1 100644 --- a/projects/Win/vc14/gtest-intrusive-set.vcxproj +++ b/projects/Win/vc14/gtest-intrusive-set.vcxproj @@ -27,6 +27,8 @@ + + @@ -199,6 +201,8 @@ + + diff --git a/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters b/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters index b1946eca..027cb084 100644 --- a/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters +++ b/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters @@ -171,6 +171,12 @@ Source Files\FeldmanHashSet + + Source Files\MichaelSet + + + Source Files\MichaelSet + @@ -212,5 +218,11 @@ Header Files + + Header Files + + + Header Files + \ No newline at end of file diff --git a/test/unit/intrusive-set/CMakeLists.txt b/test/unit/intrusive-set/CMakeLists.txt index a05cce67..f8c0094c 100644 --- a/test/unit/intrusive-set/CMakeLists.txt +++ b/test/unit/intrusive-set/CMakeLists.txt @@ -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 index 00000000..6a2b89ab --- /dev/null +++ b/test/unit/intrusive-set/intrusive_michael_iterable_dhp.cpp @@ -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 +#include + +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 > + ,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 > + ,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 less; + typedef cmp 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 index 00000000..4498172a --- /dev/null +++ b/test/unit/intrusive-set/intrusive_michael_iterable_hp.cpp @@ -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 +#include + +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 > + ,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 > + ,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 less; + typedef cmp 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_michael_dhp.cpp b/test/unit/intrusive-set/intrusive_michael_michael_dhp.cpp index 035c21f1..f7227182 100644 --- a/test/unit/intrusive-set/intrusive_michael_michael_dhp.cpp +++ b/test/unit/intrusive-set/intrusive_michael_michael_dhp.cpp @@ -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/intrusive_michael_michael_hp.cpp b/test/unit/intrusive-set/intrusive_michael_michael_hp.cpp index a97824d3..f408b476 100644 --- a/test/unit/intrusive-set/intrusive_michael_michael_hp.cpp +++ b/test/unit/intrusive-set/intrusive_michael_michael_hp.cpp @@ -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 index 00000000..e1507468 --- /dev/null +++ b/test/unit/intrusive-set/test_intrusive_michael_iterable.h @@ -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 +#include + +#include +#include // 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()( i ); + } + template + 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 + struct less + { + bool operator ()(const T& v1, const T& v2 ) const + { + return v1.key() < v2.key(); + } + + template + bool operator ()(const T& v1, const Q& v2 ) const + { + return v1.key() < v2; + } + + template + bool operator ()(const Q& v1, const T& v2 ) const + { + return v1 < v2.key(); + } + }; + + template + 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 + int operator ()(const T& v1, const Q& v2 ) const + { + if ( v1.key() < v2 ) + return -1; + return v1.key() > v2 ? 1 : 0; + } + + template + 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 + bool operator()( Q const& lhs, T const& rhs ) const + { + return lhs.key() < rhs.key(); + } + }; + + struct mock_disposer + { + template + void operator ()( T * p ) + { + ++p->nDisposeCount; + } + }; + + protected: + template + 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( 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 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 index 00000000..65621cf0 --- /dev/null +++ b/test/unit/intrusive-set/test_intrusive_michael_iterable_hp.h @@ -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 + 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(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 diff --git a/test/unit/list/intrusive_michael_dhp.cpp b/test/unit/list/intrusive_michael_dhp.cpp index d6de7f05..f828c3b2 100644 --- a/test/unit/list/intrusive_michael_dhp.cpp +++ b/test/unit/list/intrusive_michael_dhp.cpp @@ -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 diff --git a/test/unit/list/intrusive_michael_hp.cpp b/test/unit/list/intrusive_michael_hp.cpp index 26b0bb53..693a0bfb 100644 --- a/test/unit/list/intrusive_michael_hp.cpp +++ b/test/unit/list/intrusive_michael_hp.cpp @@ -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 diff --git a/test/unit/list/kv_michael_dhp.cpp b/test/unit/list/kv_michael_dhp.cpp index f942b96c..ee2e490b 100644 --- a/test/unit/list/kv_michael_dhp.cpp +++ b/test/unit/list/kv_michael_dhp.cpp @@ -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 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 list_type; + + cds::container::michael_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + } // namespace diff --git a/test/unit/list/kv_michael_hp.cpp b/test/unit/list/kv_michael_hp.cpp index baca4a35..2912dccc 100644 --- a/test/unit/list/kv_michael_hp.cpp +++ b/test/unit/list/kv_michael_hp.cpp @@ -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 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 list_type; + + cds::container::michael_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + } // namespace diff --git a/test/unit/list/kv_michael_nogc.cpp b/test/unit/list/kv_michael_nogc.cpp index 083aa6d5..6f81d5fe 100644 --- a/test/unit/list/kv_michael_nogc.cpp +++ b/test/unit/list/kv_michael_nogc.cpp @@ -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 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 list_type; + + cds::container::michael_list::stat<> st; + list_type l( st ); + test( l ); + test_ordered_iterator( l ); + } + } // namespace diff --git a/test/unit/list/michael_dhp.cpp b/test/unit/list/michael_dhp.cpp index 1ecabe2c..65450e98 100644 --- a/test/unit/list/michael_dhp.cpp +++ b/test/unit/list/michael_dhp.cpp @@ -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 less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::michael_list::stat<> stat; + + }; + typedef cc::MichaelList 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 less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::michael_list::wrapped_stat<> stat; + + }; + typedef cc::MichaelList list_type; + + cds::container::michael_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + } // namespace diff --git a/test/unit/list/michael_hp.cpp b/test/unit/list/michael_hp.cpp index 6a2261be..bb28f46b 100644 --- a/test/unit/list/michael_hp.cpp +++ b/test/unit/list/michael_hp.cpp @@ -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 less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::michael_list::stat<> stat; + + }; + typedef cc::MichaelList 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 less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::michael_list::wrapped_stat<> stat; + + }; + typedef cc::MichaelList list_type; + + cds::container::michael_list::stat<> st; + list_type l( st ); + test_common( l ); + test_ordered_iterator( l ); + test_hp( l ); + } + } // namespace diff --git a/test/unit/list/michael_nogc.cpp b/test/unit/list/michael_nogc.cpp index 88331cb9..4ad27ce0 100644 --- a/test/unit/list/michael_nogc.cpp +++ b/test/unit/list/michael_nogc.cpp @@ -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 less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::michael_list::stat<> stat; + }; + typedef cc::MichaelList 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 less; + typedef cds::atomicity::item_counter item_counter; + typedef cds::container::michael_list::wrapped_stat<> stat; + }; + typedef cc::MichaelList list_type; + + cds::container::michael_list::stat<> st; + list_type l{ st }; + test( l ); + test_ordered_iterator( l ); + } + } // namespace diff --git a/test/unit/list/test_intrusive_iterable_list.h b/test/unit/list/test_intrusive_iterable_list.h index 3bdfaa68..8416a4c4 100644 --- a/test/unit/list/test_intrusive_iterable_list.h +++ b/test/unit/list/test_intrusive_iterable_list.h @@ -278,11 +278,11 @@ namespace cds_test { break; case 3: { - std::pair ret = l.update( i, false ); + std::pair 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 ); } diff --git a/test/unit/list/test_intrusive_michael_rcu.h b/test/unit/list/test_intrusive_michael_rcu.h index 45b0b2a8..65924680 100644 --- a/test/unit/list/test_intrusive_michael_rcu.h +++ b/test/unit/list/test_intrusive_michael_rcu.h @@ -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 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 ); diff --git a/test/unit/list/test_kv_michael_rcu.h b/test/unit/list/test_kv_michael_rcu.h index 730049b1..54a8239b 100644 --- a/test/unit/list/test_kv_michael_rcu.h +++ b/test/unit/list/test_kv_michael_rcu.h @@ -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 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 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 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 diff --git a/test/unit/list/test_michael_rcu.h b/test/unit/list/test_michael_rcu.h index 143afc42..f0e4059a 100644 --- a/test/unit/list/test_michael_rcu.h +++ b/test/unit/list/test_michael_rcu.h @@ -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 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 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 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 -- 2.34.1