X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fcontainer%2Fimpl%2Flazy_list.h;h=96c37b814fac248c5fcc15f818c659a6c7627ac2;hb=6924946ceeaae28bc227fe7c9d8e939963bb9d69;hp=79595829e8a4bfe15fa4f4737b6dfd1b0e60086d;hpb=e98e89712907f99cbf051d0e138a8e2472d43469;p=libcds.git

diff --git a/cds/container/impl/lazy_list.h b/cds/container/impl/lazy_list.h
index 79595829..96c37b81 100644
--- a/cds/container/impl/lazy_list.h
+++ b/cds/container/impl/lazy_list.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_IMPL_LAZY_LIST_H
 #define CDSLIB_CONTAINER_IMPL_LAZY_LIST_H
@@ -112,6 +140,25 @@ 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
+
+        //@cond
+        // Rebind traits (split-list support)
+        template <typename... Options>
+        struct rebind_traits {
+            typedef LazyList<
+                gc
+                , value_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
@@ -121,42 +168,6 @@ namespace cds { namespace container {
         typedef typename maker::intrusive_traits::compare  intrusive_key_comparator;
 
         typedef typename base_class::node_type head_type;
-        //@endcond
-
-    public:
-        /// Guarded pointer
-        typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
-
-    private:
-        //@cond
-        static value_type& node_to_value( node_type& n )
-        {
-            return n.m_Value;
-        }
-        static value_type const& node_to_value( node_type const& n )
-        {
-            return n.m_Value;
-        }
-        //@endcond
-
-    protected:
-        //@cond
-        template <typename Q>
-        static node_type * alloc_node( Q const& v )
-        {
-            return cxx_allocator().New( v );
-        }
-
-        template <typename... Args>
-        static node_type * alloc_node( Args&&... args )
-        {
-            return cxx_allocator().MoveNew( std::forward<Args>(args)... );
-        }
-
-        static void free_node( node_type * pNode )
-        {
-            cxx_allocator().Delete( pNode );
-        }
 
         struct node_disposer {
             void operator()( node_type * pNode )
@@ -164,35 +175,20 @@ namespace cds { namespace container {
                 free_node( pNode );
             }
         };
-        typedef std::unique_ptr< node_type, node_disposer >     scoped_node_ptr;
+        typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
 
-        head_type& head()
-        {
-            return base_class::m_Head;
-        }
-
-        head_type const& head() const
-        {
-            return base_class::m_Head;
-        }
-
-        head_type& tail()
-        {
-            return base_class::m_Tail;
-        }
-
-        head_type const&  tail() const
-        {
-            return base_class::m_Tail;
-        }
         //@endcond
 
+    public:
+        /// Guarded pointer
+        typedef typename gc::template guarded_ptr< node_type, value_type, details::guarded_ptr_cast_set<node_type, value_type> > guarded_ptr;
+
     protected:
-                //@cond
+        //@cond
         template <bool IsConst>
         class iterator_type: protected base_class::template iterator_type<IsConst>
         {
-            typedef typename base_class::template iterator_type<IsConst>    iterator_base;
+            typedef typename base_class::template iterator_type<IsConst> iterator_base;
 
             iterator_type( head_type const& pNode )
                 : iterator_base( const_cast<head_type *>( &pNode ))
@@ -211,7 +207,7 @@ namespace cds { namespace container {
             iterator_type()
             {}
 
-            iterator_type( const iterator_type& src )
+            iterator_type( iterator_type const& src )
                 : iterator_base( src )
             {}
 
@@ -247,6 +243,8 @@ namespace cds { namespace container {
         //@endcond
 
     public:
+    ///@name Forward iterators (only for debugging purpose)
+    //@{
         /// Forward iterator
         /**
             The forward iterator for lazy list has some features:
@@ -257,9 +255,9 @@ namespace cds { namespace container {
             - The iterator cannot be moved across thread boundary since it contains 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 list.
+              Moreover, a crash is possible when you try to iterate the next element that has been deleted by concurrent thread.
 
-            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.
         */
         typedef iterator_type<false>    iterator;
 
@@ -275,7 +273,7 @@ namespace cds { namespace container {
         */
         iterator begin()
         {
-            iterator it( head() );
+            iterator it( head());
             ++it        ;   // skip dummy head node
             return it;
         }
@@ -289,42 +287,50 @@ namespace cds { namespace container {
         */
         iterator end()
         {
-            return iterator( tail() );
+            return iterator( tail());
         }
 
         /// Returns a forward const iterator addressing the first element in a list
-        //@{
         const_iterator begin() const
         {
-            const_iterator it( head() );
+            const_iterator it( head());
             ++it        ;   // skip dummy head node
             return it;
         }
+
+        /// Returns a forward const iterator addressing the first element in a list
         const_iterator cbegin() const
         {
-            const_iterator it( head() );
+            const_iterator it( head());
             ++it        ;   // skip dummy head node
             return it;
         }
-        //@}
 
         /// Returns an const iterator that addresses the location succeeding the last element in a list
-        //@{
         const_iterator end() const
         {
-            return const_iterator( tail() );
+            return const_iterator( tail());
         }
+
+        /// Returns an const iterator that addresses the location succeeding the last element in a list
         const_iterator cend() const
         {
-            return const_iterator( tail() );
+            return const_iterator( tail());
         }
-        //@}
+    //@}
 
     public:
         /// Default constructor
         LazyList()
         {}
 
+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, lazy_list::wrapped_stat<Stat>>::value >>
+        explicit LazyList( Stat& st )
+            : base_class( st )
+        {}
+        //@endcond
+
         /// Destructor clears the list
         ~LazyList()
         {
@@ -343,9 +349,9 @@ namespace cds { namespace container {
             Returns \p true if inserting successful, \p false otherwise.
         */
         template <typename Q>
-        bool insert( Q const& val )
+        bool insert( Q&& val )
         {
-            return insert_at( head(), val );
+            return insert_at( head(), std::forward<Q>( val ));
         }
 
         /// Inserts new node
@@ -371,9 +377,9 @@ namespace cds { namespace container {
             it is preferable that the initialization should be completed only if inserting is successful.
         */
         template <typename Q, typename Func>
-        bool insert( Q const& key, Func func )
+        bool insert( Q&& key, Func func )
         {
-            return insert_at( head(), key, func );
+            return insert_at( head(), std::forward<Q>( key ), func );
         }
 
         /// Inserts data of type \p value_type constructed from \p args
@@ -397,20 +403,20 @@ namespace cds { namespace container {
             The functor \p Func signature is:
             \code
                 struct my_functor {
-                    void operator()( bool bNew, value_type& item, Q const& val );
+                    void operator()( bool bNew, value_type& item, Q const& key );
                 };
             \endcode
 
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
             - \p item - item of the list
-            - \p val - argument \p key passed into the \p %update() function
+            - \p key - argument \p key passed into the \p %update() function
 
             The functor may change non-key fields of the \p item;
             during \p func call \p item is locked so it is safe to modify the item in
             multi-threaded environment.
 
-            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.
         */
@@ -526,9 +532,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr extract( Q 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
@@ -544,9 +548,7 @@ namespace cds { namespace container {
         guarded_ptr extract_with( Q 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
@@ -557,7 +559,7 @@ namespace cds { namespace container {
         template <typename Q>
         bool contains( Q const& key )
         {
-            return find_at( head(), key, intrusive_key_comparator() );
+            return find_at( head(), key, intrusive_key_comparator());
         }
         //@cond
         template <typename Q>
@@ -578,7 +580,7 @@ namespace cds { namespace container {
         bool contains( Q const& key, Less pred )
         {
             CDS_UNUSED( pred );
-            return find_at( head(), key, typename maker::template less_wrapper<Less>::type() );
+            return find_at( head(), key, typename maker::template less_wrapper<Less>::type());
         }
         //@cond
         template <typename Q, typename Less>
@@ -673,9 +675,7 @@ namespace cds { namespace container {
         template <typename Q>
         guarded_ptr get( Q 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 key \p key and return the item found
@@ -691,9 +691,7 @@ namespace cds { namespace container {
         guarded_ptr get_with( Q 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 whether the list is empty
@@ -715,6 +713,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()
         {
@@ -723,6 +727,58 @@ namespace cds { namespace container {
 
     protected:
         //@cond
+        static value_type& node_to_value( node_type& n )
+        {
+            return n.m_Value;
+        }
+
+        static value_type const& node_to_value( node_type const& n )
+        {
+            return n.m_Value;
+        }
+
+        template <typename Q>
+        static node_type * alloc_node( Q const& v )
+        {
+            return cxx_allocator().New( v );
+        }
+
+        template <typename... Args>
+        static node_type * alloc_node( Args&&... args )
+        {
+            return cxx_allocator().MoveNew( std::forward<Args>( args )... );
+        }
+
+        static void free_node( node_type * pNode )
+        {
+            cxx_allocator().Delete( pNode );
+        }
+
+        head_type& head()
+        {
+            return base_class::m_Head;
+        }
+
+        head_type const& head() const
+        {
+            return base_class::m_Head;
+        }
+
+        head_type& tail()
+        {
+            return base_class::m_Tail;
+        }
+
+        head_type const&  tail() const
+        {
+            return base_class::m_Tail;
+        }
+
+        bool insert_node( node_type * pNode )
+        {
+            return insert_node_at( head(), pNode );
+        }
+
         bool insert_node_at( head_type& refHead, node_type * pNode )
         {
             assert( pNode != nullptr );
@@ -737,9 +793,9 @@ namespace cds { namespace container {
         }
 
         template <typename Q>
-        bool insert_at( head_type& refHead, const Q& val )
+        bool insert_at( head_type& refHead, Q&& val )
         {
-            return insert_node_at( refHead, alloc_node( val ));
+            return insert_node_at( refHead, alloc_node( std::forward<Q>( val )));
         }
 
         template <typename... Args>
@@ -749,11 +805,11 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Func>
-        bool insert_at( head_type& refHead, const Q& key, Func f )
+        bool insert_at( head_type& refHead, Q&& key, Func f )
         {
-            scoped_node_ptr pNode( alloc_node( key ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( key )));
 
-            if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node_to_value(node) ); } )) {
+            if ( base_class::insert_at( &refHead, *pNode, [&f](node_type& node){ f( node_to_value(node)); } )) {
                 pNode.release();
                 return true;
             }
@@ -761,24 +817,24 @@ namespace cds { namespace container {
         }
 
         template <typename Q, typename Compare, typename Func>
-        bool erase_at( head_type& refHead, const Q& key, Compare cmp, Func f )
+        bool erase_at( head_type& refHead, Q const& key, Compare cmp, Func f )
         {
-            return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ f( node_to_value(node) ); } );
+            return base_class::erase_at( &refHead, key, cmp, [&f](node_type const& node){ f( node_to_value(node)); } );
         }
 
         template <typename Q, typename Compare>
-        bool extract_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
+        guarded_ptr extract_at( head_type& refHead, Q const& key, Compare cmp )
         {
-            return base_class::extract_at( &refHead, guard, key, cmp );
+            return base_class::extract_at( &refHead, key, cmp );
         }
 
         template <typename Q, typename Func>
-        std::pair<bool, bool> update_at( head_type& refHead, const Q& key, Func f, bool bAllowInsert )
+        std::pair<bool, bool> update_at( head_type& refHead, Q const& key, Func f, bool bAllowInsert )
         {
             scoped_node_ptr pNode( alloc_node( key ));
 
             std::pair<bool, bool> ret = base_class::update_at( &refHead, *pNode,
-                [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(node), key );},
+                [&f, &key](bool bNew, node_type& node, node_type&) { f( bNew, node_to_value(node), key );},
                 bAllowInsert );
             if ( ret.first && ret.second )
                 pNode.release();
@@ -795,13 +851,13 @@ namespace cds { namespace container {
         template <typename Q, typename Compare, typename Func>
         bool find_at( head_type& refHead, Q& val, Compare cmp, Func f )
         {
-            return base_class::find_at( &refHead, val, cmp, [&f](node_type& node, Q& val){ f( node_to_value(node), val ); });
+            return base_class::find_at( &refHead, val, cmp, [&f](node_type& node, Q& v){ f( node_to_value(node), v ); });
         }
 
         template <typename Q, typename Compare>
-        bool get_at( head_type& refHead, typename guarded_ptr::native_guard& guard, Q const& key, Compare cmp )
+        guarded_ptr get_at( head_type& refHead, Q const& key, Compare cmp )
         {
-            return base_class::get_at( &refHead, guard, key, cmp );
+            return base_class::get_at( &refHead, key, cmp );
         }
 
         //@endcond