X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fmichael_list_nogc.h;h=747d58db6c06e9ea67b6328f043c5b423546f4db;hb=65fe5b08577a662418660884564867944b43db40;hp=b6a48ce0d49f242517f95b754d0a9c1954ac046d;hpb=e98e89712907f99cbf051d0e138a8e2472d43469;p=libcds.git diff --git a/cds/container/michael_list_nogc.h b/cds/container/michael_list_nogc.h index b6a48ce0..747d58db 100644 --- a/cds/container/michael_list_nogc.h +++ b/cds/container/michael_list_nogc.h @@ -1,4 +1,32 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ #ifndef CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H #define CDSLIB_CONTAINER_MICHAEL_LIST_NOGC_H @@ -70,6 +98,23 @@ 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 + + //@cond + // Rebind traits (split-list support) + template + struct rebind_traits { + typedef MichaelList< + gc + , value_type + , typename cds::opt::make_options< traits, Options...>::type + > type; + }; + + // Stat selector + template + using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >; + //@endcond protected: //@cond @@ -79,30 +124,6 @@ namespace cds { namespace container { typedef typename maker::intrusive_traits::compare intrusive_key_comparator; typedef typename base_class::atomic_node_ptr head_type; - //@endcond - - protected: - //@cond - static node_type * alloc_node() - { - return cxx_allocator().New(); - } - - static node_type * alloc_node( value_type const& v ) - { - return cxx_allocator().New( v ); - } - - template - static node_type * alloc_node( Args&&... args ) - { - return cxx_allocator().MoveNew( std::forward(args)... ); - } - - static void free_node( node_type * pNode ) - { - cxx_allocator().Delete( pNode ); - } struct node_disposer { void operator()( node_type * pNode ) @@ -110,17 +131,8 @@ namespace cds { namespace container { free_node( pNode ); } }; - typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; - head_type& head() - { - return base_class::m_pHead; - } - - head_type const& head() const - { - return base_class::m_pHead; - } + typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr; //@endcond protected: @@ -194,6 +206,8 @@ namespace cds { namespace container { //@endcond public: + ///@name Forward iterators + //@{ /// Returns a forward iterator addressing the first element in a list /** For empty list \code begin() == end() \endcode @@ -212,7 +226,7 @@ namespace cds { namespace container { */ iterator begin() { - return iterator( head() ); + return iterator( head()); } /// Returns an iterator that addresses the location succeeding the last element in a list @@ -229,38 +243,29 @@ namespace cds { namespace container { } /// Returns a forward const iterator addressing the first element in a list - //@{ const_iterator begin() const { - return const_iterator( head() ); + return const_iterator( head()); } + + /// Returns a forward const iterator addressing the first element in a list const_iterator cbegin() const { - return const_iterator( head() ); + return const_iterator( head()); } - //@} /// Returns an const iterator that addresses the location succeeding the last element in a list - //@{ const_iterator end() const { return const_iterator(); } + + /// Returns an const iterator that addresses the location succeeding the last element in a list const_iterator cend() const { return const_iterator(); } - //@} - - protected: - //@cond - iterator node_to_iterator( node_type * pNode ) - { - if ( pNode ) - return iterator( *pNode ); - return end(); - } - //@endcond + //@} public: /// Default constructor @@ -270,7 +275,14 @@ namespace cds { namespace container { MichaelList() {} - /// List desctructor + //@cond + template >::value >> + explicit MichaelList( Stat& st ) + : base_class( st ) + {} + //@endcond + + /// List destructor /** Clears the list */ @@ -287,14 +299,14 @@ namespace cds { namespace container { Return an iterator pointing to inserted item if success \ref end() otherwise */ template - iterator insert( const Q& val ) + iterator insert( Q&& val ) { - return node_to_iterator( insert_at( head(), val ) ); + return node_to_iterator( insert_at( head(), std::forward( val ))); } /// Updates the item /** - If \p key is not in the list and \p bAllowInsert is \p true, + If \p key is not in the list and \p bAllowInsert is \p true, the function inserts a new item. Otherwise, the function returns an iterator pointing to the item found. @@ -303,9 +315,9 @@ namespace cds { namespace container { already is in the list. */ template - std::pair update( const Q& key, bool bAllowInsert = true ) + std::pair update( Q&& key, bool bAllowInsert = true ) { - std::pair< node_type *, bool > ret = update_at( head(), key, bAllowInsert ); + std::pair< node_type *, bool > ret = update_at( head(), std::forward( key ), bAllowInsert ); return std::make_pair( node_to_iterator( ret.first ), ret.second ); } //@cond @@ -336,7 +348,7 @@ namespace cds { namespace container { template iterator contains( Q const& key ) { - return node_to_iterator( find_at( head(), key, intrusive_key_comparator() )); + return node_to_iterator( find_at( head(), key, intrusive_key_comparator())); } //@cond template @@ -357,7 +369,7 @@ namespace cds { namespace container { iterator contains( Q const& key, Less pred ) { CDS_UNUSED( pred ); - return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper::type() ) ); + return node_to_iterator( find_at( head(), key, typename maker::template less_wrapper::type())); } //@cond template @@ -387,6 +399,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() { @@ -395,6 +413,54 @@ namespace cds { namespace container { protected: //@cond + static value_type& node_to_value( node_type& n ) + { + return n.m_Value; + } + + static node_type * alloc_node() + { + return cxx_allocator().New(); + } + + static node_type * alloc_node( value_type const& v ) + { + return cxx_allocator().New( v ); + } + + template + static node_type * alloc_node( Args&&... args ) + { + return cxx_allocator().MoveNew( std::forward( args )... ); + } + + static void free_node( node_type * pNode ) + { + cxx_allocator().Delete( pNode ); + } + + head_type& head() + { + return base_class::m_pHead; + } + + head_type const& head() const + { + return base_class::m_pHead; + } + + iterator node_to_iterator( node_type * pNode ) + { + if ( pNode ) + return iterator( *pNode ); + return end(); + } + + iterator insert_node( node_type * pNode ) + { + return node_to_iterator( insert_node_at( head(), pNode )); + } + node_type * insert_node_at( head_type& refHead, node_type * pNode ) { assert( pNode != nullptr ); @@ -406,23 +472,22 @@ namespace cds { namespace container { } template - node_type * insert_at( head_type& refHead, const Q& val ) + node_type * insert_at( head_type& refHead, Q&& val ) { - return insert_node_at( refHead, alloc_node( val )); + return insert_node_at( refHead, alloc_node( std::forward( val ))); } template - std::pair< node_type *, bool > update_at( head_type& refHead, const Q& val, bool bAllowInsert ) + std::pair< node_type *, bool > update_at( head_type& refHead, Q&& val, bool bAllowInsert ) { - scoped_node_ptr pNode( alloc_node( val )); + scoped_node_ptr pNode( alloc_node( std::forward( val ))); node_type * pItemFound = nullptr; std::pair ret = base_class::update_at( refHead, *pNode, [&pItemFound](bool, node_type& item, node_type&) { pItemFound = &item; }, bAllowInsert ); - assert( pItemFound != nullptr ); - if ( ret.first && ret.second ) + if ( ret.second ) pNode.release(); return std::make_pair( pItemFound, ret.second ); } @@ -438,7 +503,6 @@ namespace cds { namespace container { { return base_class::find_at( refHead, key, cmp ); } - //@endcond }; }} // namespace cds::container