Removed trailing spaces

[libcds.git] / cds / container / impl / michael_kvlist.h

diff --git a/cds/container/impl/michael_kvlist.h b/cds/container/impl/michael_kvlist.h
index 9b3a3595150ec15cae7ba00f8dd0257a1195f97e..72602e10fda9549d185e6d4a1378c15fceb352ef 100644 (file)
--- a/cds/container/impl/michael_kvlist.h
+++ b/cds/container/impl/michael_kvlist.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-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 CDSLIB_CONTAINER_IMPL_MICHAEL_KVLIST_H
 #define CDSLIB_CONTAINER_IMPL_MICHAEL_KVLIST_H
 
 #ifndef CDSLIB_CONTAINER_IMPL_MICHAEL_KVLIST_H
 #define CDSLIB_CONTAINER_IMPL_MICHAEL_KVLIST_H


@@ -8,7 +36,7 @@
 
 namespace cds { namespace container {
 
 
 namespace cds { namespace container {
 

-    /// Michael's ordered list fo key-value pair
+    /// Michael's ordered list for key-value pair

     /** @ingroup cds_nonintrusive_list
         \anchor cds_nonintrusive_MichaelKVList_gc
 
     /** @ingroup cds_nonintrusive_list
         \anchor cds_nonintrusive_MichaelKVList_gc
 


@@ -26,7 +54,7 @@ namespace cds { namespace container {
         - \p Value - value type stored in a list
         - \p Traits - type traits, default is \p michael_list::traits
 
         - \p Value - value type stored in a list
         - \p Traits - type traits, default is \p michael_list::traits
 

-        It is possible to declare option-based list with \p cds::container::michael_list::make_traits metafunction istead of \p Traits template
+        It is possible to declare option-based list with \p cds::container::michael_list::make_traits metafunction instead of \p Traits template

         argument. For example, the following traits-based declaration of \p gc::HP Michael's list
         \code
         #include <cds/container/michael_kvlist_hp.h>
         argument. For example, the following traits-based declaration of \p gc::HP Michael's list
         \code
         #include <cds/container/michael_kvlist_hp.h>


@@ -103,11 +131,31 @@ namespace cds { namespace container {
 #endif
 
         typedef typename base_class::gc           gc;             ///< Garbage collector used
 #endif
 
         typedef typename base_class::gc           gc;             ///< Garbage collector used

+        typedef Traits                            traits;         ///< List traits

         typedef typename base_class::back_off     back_off;       ///< Back-off strategy used
         typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
         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::back_off     back_off;       ///< Back-off strategy used
         typedef typename maker::allocator_type    allocator_type; ///< Allocator type used for allocate/deallocate the nodes
         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
+
+        //@cond
+        // Rebind traits (split-list support)
+        template <typename... Options>
+        struct rebind_traits {
+            typedef MichaelKVList<
+                gc
+                , key_type, mapped_type
+                , typename cds::opt::make_options< traits, Options...>::type
+            > type;
+        };
+
+        // Stat selector
+        template <typename Stat>
+        using select_stat_wrapper = typename base_class::template select_stat_wrapper< Stat >;
+        //@endcond

 
     protected:
         //@cond
 
     protected:
         //@cond


@@ -252,8 +300,7 @@ namespace cds { namespace container {
             - 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 list.
 
             - 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 list.
 

-            Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
-            for debug purpose only.
+            @warning Use this iterator on the concurrent container for debugging purpose only.

 
             The iterator interface to access item data:
             - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator
 
             The iterator interface to access item data:
             - <tt> operator -> </tt> - returns a pointer to \ref value_type for iterator


@@ -271,6 +318,8 @@ namespace cds { namespace container {
         */
         typedef iterator_type<true>     const_iterator;
 
         */
         typedef iterator_type<true>     const_iterator;
 

+    ///@name Forward iterators (only for debugging purpose)
+    //@{

         /// Returns a forward iterator addressing the first element in a list
         /**
             For empty list \code begin() == end() \endcode
         /// Returns a forward iterator addressing the first element in a list
         /**
             For empty list \code begin() == end() \endcode


@@ -294,28 +343,29 @@ namespace cds { namespace container {
         }
 
         /// Returns a forward const iterator addressing the first element in a list
         }
 
         /// Returns a forward const iterator addressing the first element in a list

-        //@{

         const_iterator begin() const
         {
             return const_iterator( head() );
         }
         const_iterator begin() const
         {
             return const_iterator( head() );
         }

+
+        /// Returns a forward const iterator addressing the first element in a list

         const_iterator cbegin() const
         {
             return const_iterator( head() );
         }
         const_iterator cbegin() const
         {
             return const_iterator( head() );
         }

-        //@}

 
         /// Returns an const iterator that addresses the location succeeding the last element in a list
 
         /// Returns an const iterator that addresses the location succeeding the last element in a list

-        //@{

         const_iterator end() const
         {
             return const_iterator();
         }
         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();
         }
         const_iterator cend() const
         {
             return const_iterator();
         }

-        //@}
+    //@}

 
     public:
         /// Default constructor
 
     public:
         /// Default constructor


@@ -325,7 +375,14 @@ namespace cds { namespace container {
         MichaelKVList()
         {}
 
         MichaelKVList()
         {}
 

-        /// List desctructor
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, michael_list::wrapped_stat<Stat>>::value >>
+        explicit MichaelKVList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
+        /// List destructor

         /**
             Clears the list
         */
         /**
             Clears the list
         */


@@ -346,9 +403,9 @@ namespace cds { namespace container {
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename K>
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename K>

-        bool insert( const K& key )
+        bool insert( K&& key )

         {
         {

-            return insert_at( head(), key );
+            return insert_at( head(), std::forward<K>( key ));

         }
 
         /// Inserts new node with a key and a value
         }
 
         /// Inserts new node with a key and a value


@@ -362,12 +419,12 @@ namespace cds { namespace container {
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename K, typename V>
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename K, typename V>

-        bool insert( const K& key, const V& val )
+        bool insert( K&& key, V&& val )

         {
             // We cannot use insert with functor here
             // because we cannot lock inserted node for updating
             // Therefore, we use separate function
         {
             // We cannot use insert with functor here
             // because we cannot lock inserted node for updating
             // Therefore, we use separate function

-            return insert_at( head(), key, val );
+            return insert_at( head(), std::forward<K>( key ), std::forward<V>( val ));

         }
 
         /// Inserts new node and initialize it by a functor
         }
 
         /// Inserts new node and initialize it by a functor


@@ -399,9 +456,9 @@ namespace cds { namespace container {
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename K, typename Func>
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename K, typename Func>

-        bool insert_with( const K& key, Func func )
+        bool insert_with( K&& key, Func func )

         {
         {

-            return insert_with_at( head(), key, func );
+            return insert_with_at( head(), std::forward<K>( key ), func );

         }
 
         /// Updates data by \p key
         }
 
         /// Updates data by \p key


@@ -427,16 +484,16 @@ namespace cds { namespace container {
             however, \p func must guarantee that during changing no any other modifications
             could be made on this item by concurrent threads.
 
             however, \p func must guarantee that during changing no any other modifications
             could be made on this item by concurrent threads.
 

-            Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
+            Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successful,

             \p second is true if new item has been added or \p false if the item with \p key
             already exists.
 
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename K, typename Func>
             \p second is true if new item has been added or \p false if the item with \p key
             already exists.
 
             @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
         */
         template <typename K, typename Func>

-        std::pair<bool, bool> update( K const& key, Func f, bool bAllowInsert = true )
+        std::pair<bool, bool> update( K&& key, Func f, bool bAllowInsert = true )

         {
         {

-            return update_at( head(), key, f, bAllowInsert );
+            return update_at( head(), std::forward<K>( key ), f, bAllowInsert );

         }
         //@cond
         template <typename K, typename Func>
         }
         //@cond
         template <typename K, typename Func>


@@ -552,9 +609,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr extract( K const& key )
         {
         template <typename K>
         guarded_ptr extract( K const& key )
         {

-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return extract_at( head(), key, intrusive_key_comparator() );

         }
 
         /// Extracts the item from the list with comparing functor \p pred
         }
 
         /// Extracts the item from the list with comparing functor \p pred


@@ -570,9 +625,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
         guarded_ptr extract_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );

-            guarded_ptr gp;
-            extract_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return extract_at( head(), key, typename maker::template less_wrapper<Less>::type() );

         }
 
         /// Checks whether the list contains \p key
         }
 
         /// Checks whether the list contains \p key


@@ -660,9 +713,6 @@ namespace cds { namespace container {
             and returns it as \p guarded_ptr.
             If \p key is not found the function returns an empty guarded pointer.
 
             and returns it as \p guarded_ptr.
             If \p key is not found the function returns an empty guarded pointer.
 

-            The \p disposer specified in \p Traits class template parameter is called
-            by garbage collector \p GC automatically when returned \p guarded_ptr object
-            will be destroyed or released.

             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 
             Usage:
             @note Each \p guarded_ptr object uses one GC's guard which can be limited resource.
 
             Usage:


@@ -686,9 +736,7 @@ namespace cds { namespace container {
         template <typename K>
         guarded_ptr get( K const& key )
         {
         template <typename K>
         guarded_ptr get( K const& key )
         {

-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, intrusive_key_comparator() );
-            return gp;
+            return get_at( head(), key, intrusive_key_comparator() );

         }
 
         /// Finds the \p key and return the item found
         }
 
         /// Finds the \p key and return the item found


@@ -704,9 +752,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );
         guarded_ptr get_with( K const& key, Less pred )
         {
             CDS_UNUSED( pred );

-            guarded_ptr gp;
-            get_at( head(), gp.guard(), key, typename maker::template less_wrapper<Less>::type() );
-            return gp;
+            return get_at( head(), key, typename maker::template less_wrapper<Less>::type() );

         }
 
         /// Checks if the list is empty
         }
 
         /// Checks if the list is empty


@@ -734,6 +780,12 @@ namespace cds { namespace container {
             base_class::clear();
         }
 
             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 )
     protected:
         //@cond
         bool insert_node_at( head_type& refHead, node_type * pNode )


@@ -748,21 +800,21 @@ namespace cds { namespace container {
         }
 
         template <typename K>
         }
 
         template <typename K>

-        bool insert_at( head_type& refHead, const K& key )
+        bool insert_at( head_type& refHead, K&& key )

         {
         {

-            return insert_node_at( refHead, alloc_node( key ));
+            return insert_node_at( refHead, alloc_node( std::forward<K>( key )));

         }
 
         template <typename K, typename V>
         }
 
         template <typename K, typename V>

-        bool insert_at( head_type& refHead, const K& key, const V& val )
+        bool insert_at( head_type& refHead, K&& key, V&& val )

         {
         {

-            return insert_node_at( refHead, alloc_node( key, val ));
+            return insert_node_at( refHead, alloc_node( std::forward<K>( key ), std::forward<V>( val )));

         }
 
         template <typename K, typename Func>
         }
 
         template <typename K, typename Func>

-        bool insert_with_at( head_type& refHead, const K& key, Func f )
+        bool insert_with_at( head_type& refHead, K&& key, Func f )

         {
         {

-            scoped_node_ptr pNode( alloc_node( key ));
+            scoped_node_ptr pNode( alloc_node( std::forward<K>( key )));

 
             if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); })) {
                 pNode.release();
 
             if ( base_class::insert_at( refHead, *pNode, [&f](node_type& node){ f( node.m_Data ); })) {
                 pNode.release();


@@ -778,9 +830,9 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Func>
         }
 
         template <typename K, typename Func>

-        std::pair<bool, bool> update_at( head_type& refHead, const K& key, Func f, bool bAllowInsert )
+        std::pair<bool, bool> update_at( head_type& refHead, K&& key, Func f, bool bAllowInsert )

         {
         {

-            scoped_node_ptr pNode( alloc_node( key ));
+            scoped_node_ptr pNode( alloc_node( std::forward<K>( key )));

 
             std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
                 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); },
 
             std::pair<bool, bool> ret = base_class::update_at( refHead, *pNode,
                 [&f]( bool bNew, node_type& node, node_type& ){ f( bNew, node.m_Data ); },


@@ -803,9 +855,9 @@ namespace cds { namespace container {
             return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
         }
         template <typename K, typename Compare>
             return base_class::erase_at( refHead, key, cmp, [&f]( node_type const & node ){ f( const_cast<value_type&>(node.m_Data)); });
         }
         template <typename K, typename Compare>

-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, K const& key, Compare cmp )

         {
         {

-            return base_class::extract_at( refHead, guard, key, cmp );
+            return base_class::extract_at( refHead, key, cmp );

         }
 
         template <typename K, typename Compare>
         }
 
         template <typename K, typename Compare>


@@ -821,9 +873,9 @@ namespace cds { namespace container {
         }
 
         template <typename K, typename Compare>
         }
 
         template <typename K, typename Compare>

-        bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, K const& key, Compare cmp )
+        guarded_ptr get_at( head_type& refHead, K const& key, Compare cmp )

         {
         {

-            return base_class::get_at( refHead, guard, key, cmp );
+            return base_class::get_at( refHead, key, cmp );

         }
 
         //@endcond
         }
 
         //@endcond