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

diff --git a/cds/container/impl/lazy_list.h b/cds/container/impl/lazy_list.h
index 6cfafc29..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
@@ -10,7 +38,7 @@ namespace cds { namespace container {
 
     /// Lazy ordered list
     /** @ingroup cds_nonintrusive_list
-        \anchor cds_nonintrusive_LazyList_gc
+        @anchor cds_nonintrusive_LazyList_gc
 
         Usually, ordered single-linked list is used as a building block for the hash table implementation.
         The complexity of searching is <tt>O(N)</tt>.
@@ -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;
-
-        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;
-        }
+        typedef std::unique_ptr< node_type, node_disposer > scoped_node_ptr;
 
-        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
@@ -386,36 +392,47 @@ namespace cds { namespace container {
             return emplace_at( head(), std::forward<Args>(args)... );
         }
 
-        /// Ensures that the \p key exists in the list
+        /// Updates data by \p key
         /**
-            The operation performs inserting or changing data with lock-free manner.
+            The operation performs inserting or replacing the element with lock-free manner.
 
             If the \p key not found in the list, then the new item created from \p key
-            is inserted into the list. Otherwise, the functor \p f is called with the item found.
-            \p Func signature is:
+            will be inserted iff \p bAllowInsert is \p true.
+            Otherwise, if \p key is found, the functor \p func is called with item found.
+
+            The functor \p Func signature is:
             \code
                 struct my_functor {
-                    void operator()( bool bNew, value_type& item, const Q& key );
+                    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 - an item of the list
-            - \p key - argument \p key passed into the \p %ensure() function
+            - \p item - item of the list
+            - \p key - argument \p key passed into the \p %update() function
 
-            The functor may change non-key fields of the \p item.
-            When \p func is called it has exclusive access to the item.
+            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 is in the list.
+            already exists.
         */
         template <typename Q, typename Func>
+        std::pair<bool, bool> update( Q const& key, Func func, bool bAllowInsert = true )
+        {
+            return update_at( head(), key, func, bAllowInsert );
+        }
+        //@cond
+        template <typename Q, typename Func>
+        CDS_DEPRECATED("ensure() is deprecated, use update()")
         std::pair<bool, bool> ensure( Q const& key, Func f )
         {
-            return ensure_at( head(), key, f );
+            return update( key, f, true );
         }
+        //@endcond
 
         /// Deletes \p key from the list
         /** \anchor cds_nonintrusive_LazyList_hp_erase_val
@@ -515,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
@@ -533,36 +548,48 @@ 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());
         }
 
-        /// Finds the key \p key
-        /** \anchor cds_nonintrusive_LazyList_hp_find_val
+        /// Checks whether the list contains \p key
+        /**
             The function searches the item with key equal to \p key
-            and returns \p true if it is found, and \p false otherwise
+            and returns \p true if it is found, and \p false otherwise.
         */
         template <typename Q>
+        bool contains( Q const& key )
+        {
+            return find_at( head(), key, intrusive_key_comparator());
+        }
+        //@cond
+        template <typename Q>
+        CDS_DEPRECATED("deprecated, use contains()")
         bool find( Q const& key )
         {
-            return find_at( head(), key, intrusive_key_comparator() );
+            return contains( key );
         }
+        //@endcond
 
-        /// Finds the key \p key using \p pred predicate for searching
+        /// Checks whether the list contains \p key using \p pred predicate for searching
         /**
-            The function is an analog of \ref cds_nonintrusive_LazyList_hp_find_val "find(Q const&)"
-            but \p pred is used for key comparing.
+            The function is an analog of <tt>contains( key )</tt> 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 list.
         */
         template <typename Q, typename Less>
-        bool find_with( Q const& key, Less pred )
+        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>
+        CDS_DEPRECATED("deprecated, use contains()")
+        bool find_with( Q const& key, Less pred )
+        {
+            return contains( key, pred );
+        }
+        //@endcond
         /// Finds the key \p key and performs an action with it
         /** \anchor cds_nonintrusive_LazyList_hp_find_func
             The function searches an item with key equal to \p key and calls the functor \p f for the item found.
@@ -648,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
@@ -666,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
@@ -690,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()
         {
@@ -698,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 );
@@ -712,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>
@@ -724,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;
             }
@@ -736,24 +817,25 @@ 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> ensure_at( head_type& refHead, const Q& key, Func f )
+        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::ensure_at( &refHead, *pNode,
-                [&f, &key](bool bNew, node_type& node, node_type&){f( bNew, node_to_value(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 );},
+                bAllowInsert );
             if ( ret.first && ret.second )
                 pNode.release();
 
@@ -769,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