Adds sequential barrier driver

[libcds.git] / cds / container / michael_map.h

diff --git a/cds/container/michael_map.h b/cds/container/michael_map.h
index 71287e4dd58cdeda8bfb3c592e22fc6c4d73d9b0..9947409d7643e722d8e72eb3e362c15b0ec4507c 100644 (file)
--- a/cds/container/michael_map.h
+++ b/cds/container/michael_map.h
@@ -1,7 +1,7 @@
 /*
     This file is a part of libcds - Concurrent Data Structures library
 
-    (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+    (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/
@@ -171,10 +171,6 @@ namespace cds { namespace container {
         // GC and OrderedList::gc must be the same
         static_assert( std::is_same<gc, typename ordered_list::gc>::value, "GC and OrderedList::gc must be the same");
 
-        // atomicity::empty_item_counter is not allowed as a item counter
-        static_assert( !std::is_same<item_counter, atomicity::empty_item_counter>::value,
-                        "atomicity::empty_item_counter is not allowed as a item counter");
-
         static CDS_CONSTEXPR const size_t c_nHazardPtrCount = ordered_list::c_nHazardPtrCount; ///< Count of hazard pointer required
 
         //@cond
@@ -194,8 +190,8 @@ namespace cds { namespace container {
         //@cond
         const size_t            m_nHashBitmask;
         internal_bucket_type*   m_Buckets;     ///< bucket table
-        item_counter            m_ItemCounter; ///< Item counter
         hash                    m_HashFunctor; ///< Hash functor
+        item_counter            m_ItemCounter; ///< Item counter
         stat                    m_Stat;        ///< Internal statistics
         //@endcond
 
@@ -203,7 +199,7 @@ namespace cds { namespace container {
         //@cond
         /// Forward iterator
         template <bool IsConst>
-        class iterator_type: private cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
+        class iterator_type: protected cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >
         {
             typedef cds::intrusive::michael_set::details::iterator< internal_bucket_type, IsConst >  base_class;
             friend class MichaelHashMap;
@@ -275,13 +271,13 @@ namespace cds { namespace container {
 
             /// Equality operator
             template <bool C>
-            bool operator ==(iterator_type<C> const& i )
+            bool operator ==(iterator_type<C> const& i ) const
             {
                 return base_class::operator ==( i );
             }
             /// Equality operator
             template <bool C>
-            bool operator !=(iterator_type<C> const& i )
+            bool operator !=(iterator_type<C> const& i ) const
             {
                 return !( *this == i );
             }
@@ -402,7 +398,7 @@ namespace cds { namespace container {
             size_t nLoadFactor      ///< load factor: estimation of max number of items in the bucket
             )
             : m_nHashBitmask( michael_map::details::init_hash_bitmask( nMaxItemCount, nLoadFactor ))
-            , m_Buckets( bucket_table_allocator().allocate( bucket_count()) )
+            , m_Buckets( bucket_table_allocator().allocate( bucket_count()))
         {
             for ( auto it = m_Buckets, itEnd = m_Buckets + bucket_count(); it != itEnd; ++it )
                 construct_bucket<bucket_stat>( it );
@@ -674,6 +670,34 @@ namespace cds { namespace container {
             return bRet;
         }
 
+        /// Deletes the item pointed by iterator \p iter (only for \p IterableList based map)
+        /**
+            Returns \p true if the operation is successful, \p false otherwise.
+            The function can return \p false if the node the iterator points to has already been deleted
+            by other thread.
+
+            The function does not invalidate the iterator, it remains valid and can be used for further traversing.
+
+            @note \p %erase_at() is supported only for \p %MichaelHashMap based on \p IterableList.
+        */
+#ifdef CDS_DOXYGEN_INVOKED
+        bool erase_at( iterator const& iter )
+#else
+        template <typename Iterator>
+        typename std::enable_if< std::is_same<Iterator, iterator>::value && is_iterable_list< ordered_list >::value, bool >::type
+        erase_at( Iterator const& iter )
+#endif
+        {
+            assert( iter != end());
+            assert( iter.bucket() != nullptr );
+
+            if ( iter.bucket()->erase_at( iter.underlying_iterator())) {
+                --m_ItemCounter;
+                return true;
+            }
+            return false;
+        }
+
         /// Extracts the item with specified \p key
         /** \anchor cds_nonintrusive_MichaelHashMap_hp_extract
             The function searches an item with key equal to \p key,
@@ -892,8 +916,8 @@ namespace cds { namespace container {
 
         /// Checks if the map is empty
         /**
-            Emptiness is checked by item counting: if item count is zero then the map is empty.
-            Thus, the correct item counting is an important part of the map implementation.
+            @warning If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+            the function always returns \p true.
         */
         bool empty() const
         {
@@ -901,6 +925,10 @@ namespace cds { namespace container {
         }
 
         /// Returns item count in the map
+        /**
+            If you use \p atomicity::empty_item_counter in \p traits::item_counter,
+            the function always returns 0.
+        */
         size_t size() const
         {
             return m_ItemCounter;
@@ -962,15 +990,15 @@ namespace cds { namespace container {
         }
 
         template <typename Stat>
-        typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
+        typename std::enable_if< Stat::empty >::type construct_bucket( internal_bucket_type* b )
         {
-            new (bucket) internal_bucket_type;
+            new (b) internal_bucket_type;
         }
 
         template <typename Stat>
-        typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* bucket )
+        typename std::enable_if< !Stat::empty >::type construct_bucket( internal_bucket_type* b )
         {
-            new (bucket) internal_bucket_type( m_Stat );
+            new (b) internal_bucket_type( m_Stat );
         }
         //@endcond
     };