projects / libcds.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
dummy_node renamed to aux_node
[libcds.git] / cds / intrusive / split_list_rcu.h
diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h
index 94088046cf9ceedb4f0fb5e4c0f5d9ac1752bf15..6f264cceb5c8f2bcd052ee058de96df6ecaa7cbd 100644 (file)
--- a/cds/intrusive/split_list_rcu.h
+++ b/cds/intrusive/split_list_rcu.h
@@ -126,7 +126,7 @@ namespace cds { namespace intrusive {
     protected:
         typedef typename ordered_list::node_type    list_node_type;  ///< Node type as declared in ordered list
         typedef split_list::node<list_node_type>    node_type;       ///< split-list node type
-        typedef node_type                           dummy_node_type; ///< dummy node type
+        typedef node_type                           aux_node_type; ///< dummy node type
 
         /// Split-list node traits
         /**
@@ -140,7 +140,7 @@ namespace cds { namespace intrusive {
         typedef typename split_list::details::bucket_table_selector<
             traits::dynamic_bucket_table
             , gc
-            , dummy_node_type
+            , aux_node_type
             , opt::allocator< typename traits::allocator >
             , opt::memory_model< memory_model >
         >::type bucket_table;
@@ -156,7 +156,7 @@ namespace cds { namespace intrusive {
             typedef typename base_class::auxiliary_head bucket_head_type;
 
         public:
-            bool insert_at( dummy_node_type * pHead, value_type& val )
+            bool insert_at( aux_node_type * pHead, value_type& val )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -164,7 +164,7 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Func>
-            bool insert_at( dummy_node_type * pHead, value_type& val, Func f )
+            bool insert_at( aux_node_type * pHead, value_type& val, Func f )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -172,14 +172,14 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Func>
-            std::pair<bool, bool> update_at( dummy_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
+            std::pair<bool, bool> update_at( aux_node_type * pHead, value_type& val, Func func, bool bAllowInsert )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
                 return base_class::update_at( h, val, func, bAllowInsert );
             }
 
-            bool unlink_at( dummy_node_type * pHead, value_type& val )
+            bool unlink_at( aux_node_type * pHead, value_type& val )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -187,7 +187,7 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare, typename Func>
-            bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
+            bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp, Func f )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -195,7 +195,7 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare>
-            bool erase_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
+            bool erase_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const& val, Compare cmp )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -203,7 +203,7 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare>
-            value_type * extract_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
+            value_type * extract_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -211,7 +211,7 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare, typename Func>
-            bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
+            bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp, Func f )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -219,7 +219,7 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare>
-            bool find_at( dummy_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
+            bool find_at( aux_node_type * pHead, split_list::details::search_value_type<Q> const & val, Compare cmp )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
@@ -227,18 +227,18 @@ namespace cds { namespace intrusive {
             }
 
             template <typename Q, typename Compare>
-            raw_ptr get_at( dummy_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
+            raw_ptr get_at( aux_node_type * pHead, split_list::details::search_value_type<Q>& val, Compare cmp )
             {
                 assert( pHead != nullptr );
                 bucket_head_type h(pHead);
                 return base_class::get_at( h, val, cmp );
             }
 
-            bool insert_aux_node( dummy_node_type * pNode )
+            bool insert_aux_node( aux_node_type * pNode )
             {
                 return base_class::insert_aux_node( pNode );
             }
-            bool insert_aux_node( dummy_node_type * pHead, dummy_node_type * pNode )
+            bool insert_aux_node( aux_node_type * pHead, aux_node_type * pNode )
             {
                 bucket_head_type h(pHead);
                 return base_class::insert_aux_node( h, pNode );
@@ -275,16 +275,16 @@ namespace cds { namespace intrusive {
 
     protected:
         //@cond
-        typedef cds::details::Allocator< dummy_node_type, typename traits::allocator >   dummy_node_allocator;
+        typedef cds::details::Allocator< aux_node_type, typename traits::allocator >   aux_node_allocator;
 
-        dummy_node_type * alloc_dummy_node( size_t nHash )
+        aux_node_type * alloc_aux_node( size_t nHash )
         {
             m_Stat.onHeadNodeAllocated();
-            return dummy_node_allocator().New( nHash );
+            return aux_node_allocator().New( nHash );
         }
-        void free_dummy_node( dummy_node_type * p )
+        void free_aux_node( aux_node_type * p )
         {
-            dummy_node_allocator().Delete( p );
+            aux_node_allocator().Delete( p );
             m_Stat.onHeadNodeFreed();
         }
 
@@ -306,12 +306,12 @@ namespace cds { namespace intrusive {
             return nBucket & ~( 1 << bitop::MSBnz( nBucket ) );
         }
 
-        dummy_node_type * init_bucket( size_t nBucket )
+        aux_node_type * init_bucket( size_t nBucket )
         {
             assert( nBucket > 0 );
             size_t nParent = parent_bucket( nBucket );
 
-            dummy_node_type * pParentBucket = m_Buckets.bucket( nParent );
+            aux_node_type * pParentBucket = m_Buckets.bucket( nParent );
             if ( pParentBucket == nullptr ) {
                 pParentBucket = init_bucket( nParent );
                 m_Stat.onRecursiveInitBucket();
@@ -321,13 +321,13 @@ namespace cds { namespace intrusive {
 
             // Allocate a dummy node for new bucket
             {
-                dummy_node_type * pBucket = alloc_dummy_node( split_list::dummy_hash( nBucket ) );
+                aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) );
                 if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) {
                     m_Buckets.bucket( nBucket, pBucket );
                     m_Stat.onNewBucket();
                     return pBucket;
                 }
-                free_dummy_node( pBucket );
+                free_aux_node( pBucket );
             }
 
             // Another thread set the bucket. Wait while it done
@@ -339,19 +339,19 @@ namespace cds { namespace intrusive {
             m_Stat.onBucketInitContenton();
             back_off bkoff;
             while ( true ) {
-                dummy_node_type volatile * p = m_Buckets.bucket( nBucket );
+                aux_node_type volatile * p = m_Buckets.bucket( nBucket );
                 if ( p != nullptr )
-                    return const_cast<dummy_node_type *>( p );
+                    return const_cast<aux_node_type *>( p );
                 bkoff();
                 m_Stat.onBusyWaitBucketInit();
             }
         }
 
-        dummy_node_type * get_bucket( size_t nHash )
+        aux_node_type * get_bucket( size_t nHash )
         {
             size_t nBucket = bucket_no( nHash );
 
-            dummy_node_type * pHead = m_Buckets.bucket( nBucket );
+            aux_node_type * pHead = m_Buckets.bucket( nBucket );
             if ( pHead == nullptr )
                 pHead = init_bucket( nBucket );
 
@@ -370,7 +370,7 @@ namespace cds { namespace intrusive {
                            "cds::atomicity::empty_item_counter is not allowed as a item counter");
 
             // Initialize bucket 0
-            dummy_node_type * pNode = alloc_dummy_node( 0 /*split_list::dummy_hash(0)*/ );
+            aux_node_type * pNode = alloc_aux_node( 0 /*split_list::dummy_hash(0)*/ );
 
             // insert_aux_node cannot return false for empty list
             CDS_VERIFY( m_List.insert_aux_node( pNode ));
@@ -410,7 +410,7 @@ namespace cds { namespace intrusive {
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q>  sv( val, split_list::regular_hash( nHash ));
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp,
@@ -422,7 +422,7 @@ namespace cds { namespace intrusive {
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             return m_Stat.onFind( m_List.find_at( pHead, sv, cmp ));
@@ -433,7 +433,7 @@ namespace cds { namespace intrusive {
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             raw_ptr p = m_List.get_at( pHead, sv, cmp );
@@ -446,7 +446,7 @@ namespace cds { namespace intrusive {
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             value_type * pNode = m_List.extract_at( pHead, sv, cmp );
@@ -471,7 +471,7 @@ namespace cds { namespace intrusive {
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             if ( m_List.erase_at( pHead, sv, cmp ) ) {
@@ -488,7 +488,7 @@ namespace cds { namespace intrusive {
         {
             size_t nHash = hash_value( val );
             split_list::details::search_value_type<Q const>  sv( val, split_list::regular_hash( nHash ));
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             if ( m_List.erase_at( pHead, sv, cmp, f )) {
@@ -541,7 +541,7 @@ namespace cds { namespace intrusive {
         bool insert( value_type& val )
         {
             size_t nHash = hash_value( val );
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
@@ -580,7 +580,7 @@ namespace cds { namespace intrusive {
         bool insert( value_type& val, Func f )
         {
             size_t nHash = hash_value( val );
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
@@ -616,7 +616,7 @@ namespace cds { namespace intrusive {
 
             The function applies RCU lock internally.
 
-            Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
+            Returns std::pair<bool, bool> 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 list.
 
@@ -628,7 +628,7 @@ namespace cds { namespace intrusive {
         std::pair<bool, bool> update( value_type& val, Func func, bool bAllowInsert = true )
         {
             size_t nHash = hash_value( val );
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             node_traits::to_node_ptr( val )->m_nHash = split_list::regular_hash( nHash );
@@ -636,10 +636,10 @@ namespace cds { namespace intrusive {
             std::pair<bool, bool> bRet = m_List.update_at( pHead, val, func, bAllowInsert );
             if ( bRet.first && bRet.second ) {
                 inc_item_count();
-                m_Stat.onEnsureNew();
+                m_Stat.onUpdateNew();
             }
             else
-                m_Stat.onEnsureExist();
+                m_Stat.onUpdateExist();
             return bRet;
         }
         //@cond
@@ -668,7 +668,7 @@ namespace cds { namespace intrusive {
         bool unlink( value_type& val )
         {
             size_t nHash = hash_value( val );
-            dummy_node_type * pHead = get_bucket( nHash );
+            aux_node_type * pHead = get_bucket( nHash );
             assert( pHead != nullptr );
 
             if ( m_List.unlink_at( pHead, val ) ) {
@@ -1025,19 +1025,19 @@ namespace cds { namespace intrusive {
         //@endcond
 
     public:
+    ///@name Forward iterators (thread-safe under RCU lock)
+    //@{
         /// Forward iterator
         /**
             The forward iterator for a split-list has some features:
             - it has no post-increment operator
             - it depends on iterator of underlying \p OrderedList
-            - The iterator cannot be moved across thread boundary since 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 split-list.
 
-            Therefore, the use of iterators in concurrent environment is not good idea. Use the iterator on the concurrent container
-            for debug purpose only.
+            You may safely use iterators in multi-threaded environment only under RCU lock.
+            Otherwise, a crash is possible if another thread deletes the element the iterator points to.
         */
         typedef iterator_type<false>    iterator;
+
         /// Const forward iterator
         /**
             For iterator's features and requirements see \ref iterator
@@ -1086,7 +1086,7 @@ namespace cds { namespace intrusive {
         {
             return const_iterator( m_List.cend(), m_List.cend() );
         }
-
+    //@}
     };
 
 }}  // namespace cds::intrusive
Unnamed repository; edit this file 'description' to name the repository.