Only runs standard stack test cases

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

diff --git a/cds/container/cuckoo_map.h b/cds/container/cuckoo_map.h
index b5204ffdb6f9dc8652739f4e10b965ac2a55b561..d06083e317786b95905262ebc8567c21556b6ed4 100644 (file)
--- a/cds/container/cuckoo_map.h
+++ b/cds/container/cuckoo_map.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_CUCKOO_MAP_H
 #define CDSLIB_CONTAINER_CUCKOO_MAP_H
 
 #ifndef CDSLIB_CONTAINER_CUCKOO_MAP_H
 #define CDSLIB_CONTAINER_CUCKOO_MAP_H


@@ -28,17 +56,17 @@ namespace cds { namespace container {
 
                 template <typename K>
                 node_type( K const& key )
 
                 template <typename K>
                 node_type( K const& key )

-                    : m_val( std::make_pair( key_type(key), mapped_type() ))
+                    : m_val( std::make_pair( key_type(key), mapped_type()))

                 {}
 
                 template <typename K, typename Q>
                 node_type( K const& key, Q const& v )
                 {}
 
                 template <typename K, typename Q>
                 node_type( K const& key, Q const& v )

-                    : m_val( std::make_pair( key_type(key), mapped_type(v) ))
+                    : m_val( std::make_pair( key_type(key), mapped_type(v)))

                 {}
 
                 template <typename K, typename... Args>
                 node_type( K&& key, Args&&... args )
                 {}
 
                 template <typename K, typename... Args>
                 node_type( K&& key, Args&&... args )

-                    : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)) )
+                    : m_val( std::forward<K>(key), std::move( mapped_type(std::forward<Args>(args)...)))

                 {}
             };
 
                 {}
             };
 


@@ -94,7 +122,7 @@ namespace cds { namespace container {
         <b>About Cuckoo hashing</b>
 
             [From "The Art of Multiprocessor Programming"]
         <b>About Cuckoo hashing</b>
 
             [From "The Art of Multiprocessor Programming"]

-            Cuckoo hashing is a hashing algorithm in which a newly added item displaces any earlier item
+            <a href="https://en.wikipedia.org/wiki/Cuckoo_hashing">Cuckoo hashing</a> is a hashing algorithm in which a newly added item displaces any earlier item

             occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
             N = 2k we use a two-entry array of tables, and two independent hash functions,
             <tt> h0, h1: KeyRange -> 0,...,k-1</tt>
             occupying the same slot. For brevity, a table is a k-entry array of items. For a hash set f size
             N = 2k we use a two-entry array of tables, and two independent hash functions,
             <tt> h0, h1: KeyRange -> 0,...,k-1</tt>


@@ -132,14 +160,14 @@ namespace cds { namespace container {
             the average search complexity is <tt>O(PROBE_SET/2)</tt>.
             However, the overhead of sorting can eliminate a gain of ordered search.
 
             the average search complexity is <tt>O(PROBE_SET/2)</tt>.
             However, the overhead of sorting can eliminate a gain of ordered search.
 

-            The probe set is ordered if opt::compare or opt::less is specified in \p %CuckooSet
-            declaration. Otherwise, the probe set is unordered and \p %CuckooSet must contain
-            opt::equal_to option.
+            The probe set is ordered if \p compare or \p less is specified in \p Traits
+            template parameter. Otherwise, the probe set is unordered and \p Traits must contain
+            \p equal_to predicate.

 
         Template arguments:
         - \p Key - key type
         - \p T - the type stored in the map.
 
         Template arguments:
         - \p Key - key type
         - \p T - the type stored in the map.

-        - \p Traits - map traits., default is \p cuckoo::traits.
+        - \p Traits - map traits, default is \p cuckoo::traits.

             It is possible to declare option-based set with \p cuckoo::make_traits metafunction
             result as \p Traits template argument.
 
             It is possible to declare option-based set with \p cuckoo::make_traits metafunction
             result as \p Traits template argument.
 


@@ -267,10 +295,6 @@ namespace cds { namespace container {
         /// item counter type
         typedef typename traits::item_counter  item_counter;
 
         /// item counter type
         typedef typename traits::item_counter  item_counter;
 

-        //@cond
-        typedef cds::container::cuckoo::implementation_tag implementation_tag;
-        //@endcond
-

     protected:
         //@cond
         typedef typename base_class::scoped_cell_lock   scoped_cell_lock;
     protected:
         //@cond
         typedef typename base_class::scoped_cell_lock   scoped_cell_lock;


@@ -377,7 +401,7 @@ namespace cds { namespace container {
         CuckooMap(
             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )
         CuckooMap(
             hash_tuple_type&& h     ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )

-        : base_class( std::forward<hash_tuple_type>(h) )
+        : base_class( std::forward<hash_tuple_type>(h))

         {}
 
         /// Constructs a map with given probe set properties and hash functor tuple (move semantics)
         {}
 
         /// Constructs a map with given probe set properties and hash functor tuple (move semantics)


@@ -391,7 +415,7 @@ namespace cds { namespace container {
             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )
             , unsigned int nProbesetThreshold   ///< probe set threshold, <tt>nProbesetThreshold < nProbesetSize</tt>. If 0, nProbesetThreshold = nProbesetSize - 1
             , hash_tuple_type&& h    ///< hash functor tuple of type <tt>std::tuple<H1, H2, ... Hn></tt> where <tt> n == \ref c_nArity </tt>
         )

-        : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h) )
+        : base_class( nInitialSize, nProbesetSize, nProbesetThreshold, std::forward<hash_tuple_type>(h))

         {}
 
         /// Destructor clears the map
         {}
 
         /// Destructor clears the map


@@ -486,46 +510,47 @@ namespace cds { namespace container {
             return false;
         }
 
             return false;
         }
 

-        /// Ensures that the \p key exists in the map
+        /// Updates the node

         /**
             The operation performs inserting or changing data with lock-free manner.
 
         /**
             The operation performs inserting or changing data with lock-free manner.
 

-            If the \p key not found in the map, then the new item created from \p key
-            is inserted into the map (note that in this case the \ref key_type should be
-            constructible from type \p K).
+            If \p key is not found in the map, then \p key is inserted iff \p bAllowInsert is \p true.

             Otherwise, the functor \p func is called with item found.
             Otherwise, the functor \p func is called with item found.

-            The functor \p Func may be a function with signature:
-            \code
-                void func( bool bNew, value_type& item );
-            \endcode
-            or a functor:
+            The functor \p func signature is:

             \code
                 struct my_functor {
                     void operator()( bool bNew, value_type& item );
                 };
             \endcode
             \code
                 struct my_functor {
                     void operator()( bool bNew, value_type& item );
                 };
             \endcode

-

             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise
             with arguments:
             - \p bNew - \p true if the item has been inserted, \p false otherwise

-            - \p item - item of the list
-
-            The functor may change any fields of the \p item.second that is \ref value_type.
+            - \p item - an item of the map for \p key

 
 

-            Returns <tt> std::pair<bool, bool> </tt> where \p first is true if operation is successfull,
-            \p second is true if new item has been added or \p false if the item with \p key
-            already is in the list.
+            Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
+            i.e. the node has been inserted or updated,
+            \p second is \p true if new item has been added or \p false if the item with \p key
+            already exists.

         */
         template <typename K, typename Func>
         */
         template <typename K, typename Func>

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

         {
             scoped_node_ptr pNode( alloc_node( key ));
         {
             scoped_node_ptr pNode( alloc_node( key ));

-            std::pair<bool, bool> res = base_class::ensure( *pNode,
-                [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); }
+            std::pair<bool, bool> res = base_class::update( *pNode,
+                [&func](bool bNew, node_type& item, node_type const& ){ func( bNew, item.m_val ); },
+                bAllowInsert

             );
             if ( res.first && res.second )
                 pNode.release();
             return res;
         }
             );
             if ( res.first && res.second )
                 pNode.release();
             return res;
         }

+        //@cond
+        template <typename K, typename Func>
+        CDS_DEPRECATED("ensure() is deprecated, use update()")
+        std::pair<bool, bool> ensure( K const& key, Func func )
+        {
+            return update( key, func, true );
+        }
+        //@endcond

 
         /// Delete \p key from the map
         /** \anchor cds_nonintrusive_CuckooMap_erase_val
 
         /// Delete \p key from the map
         /** \anchor cds_nonintrusive_CuckooMap_erase_val


@@ -604,7 +629,7 @@ namespace cds { namespace container {
         bool erase_with( K const& key, Predicate pred, Func f )
         {
             CDS_UNUSED( pred );
         bool erase_with( K const& key, Predicate pred, Func f )
         {
             CDS_UNUSED( pred );

-            node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
+            node_type * pNode = base_class::erase_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());

             if ( pNode ) {
                 f( pNode->m_val );
                 free_node( pNode );
             if ( pNode ) {
                 f( pNode->m_val );
                 free_node( pNode );


@@ -651,37 +676,50 @@ namespace cds { namespace container {
                 [&f](node_type& item, K const& ) { f( item.m_val );});
         }
 
                 [&f](node_type& item, K const& ) { f( item.m_val );});
         }
 

-        /// Find the key \p key
-        /** \anchor cds_nonintrusive_CuckooMap_find_val
-
+        /// Checks whether the map 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.
         */
         template <typename K>
             The function searches the item with key equal to \p key
             and returns \p true if it is found, and \p false otherwise.
         */
         template <typename K>

+        bool contains( K const& key )
+        {
+            return base_class::contains( key );
+        }
+        //@cond
+        template <typename K>
+        CDS_DEPRECATED("the function is deprecated, use contains()")

         bool find( K const& key )
         {
         bool find( K const& key )
         {

-            return base_class::find( key );
+            return contains( key );

         }
         }

+        //@endcond

 
 

-        /// Find the key \p val using \p pred predicate for comparing
+        /// Checks whether the map contains \p key using \p pred predicate for searching

         /**
         /**

-            The function is an analog of \ref cds_nonintrusive_CuckooMap_find_val "find(K const&)"
-            but \p pred is used for key comparison.
-            If you use ordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::less.
-            If you use unordered cuckoo map, then \p Predicate should have the interface and semantics like \p std::equal_to.
-            \p pred must imply the same element order as the comparator used for building the map.
+            The function is similar to <tt>contains( key )</tt> but \p pred is used for key comparing.
+            \p Less functor has the interface like \p std::less.
+            \p Less must imply the same element order as the comparator used for building the map.

         */
         template <typename K, typename Predicate>
         */
         template <typename K, typename Predicate>

-        bool find_with( K const& key, Predicate pred )
+        bool contains( K const& key, Predicate pred )

         {
             CDS_UNUSED( pred );
         {
             CDS_UNUSED( pred );

-            return base_class::find_with( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>() );
+            return base_class::contains( key, cds::details::predicate_wrapper<node_type, Predicate, key_accessor>());
+        }
+        //@cond
+        template <typename K, typename Predicate>
+        CDS_DEPRECATED("the function is deprecated, use contains()")
+        bool find_with( K const& key, Predicate pred )
+        {
+            return contains( key, pred );

         }
         }

+        //@endcond

 
         /// Clears the map
         void clear()
         {
 
         /// Clears the map
         void clear()
         {

-            base_class::clear_and_dispose( node_disposer() );
+            base_class::clear_and_dispose( node_disposer());

         }
 
         /// Checks if the map is empty
         }
 
         /// Checks if the map is empty