Merge branch 'dev' of github.com:khizmax/libcds into dev
authorkhizmax <khizmax@gmail.com>
Fri, 23 Oct 2015 10:45:48 +0000 (13:45 +0300)
committerkhizmax <khizmax@gmail.com>
Fri, 23 Oct 2015 10:45:48 +0000 (13:45 +0300)
19 files changed:
cds/container/details/feldman_hashmap_base.h
cds/container/details/feldman_hashset_base.h
cds/container/feldman_hashmap_rcu.h
cds/container/feldman_hashset_rcu.h
cds/container/impl/feldman_hashmap.h
cds/container/impl/feldman_hashset.h
cds/intrusive/details/feldman_hashset_base.h
cds/intrusive/feldman_hashset_rcu.h
cds/intrusive/impl/feldman_hashset.h
doxygen/cds.doxy
doxygen/image/feldman_hashset.png [new file with mode: 0644]
doxygen/image/multilevel_hashset.png [deleted file]
install/description.txt [deleted file]
install/post_install_script.sh [deleted file]
install/post_uninstall_script.sh [deleted file]
readme.md
tests/unit/map2/map_delodd.cpp
tests/unit/map2/map_delodd.h
tests/unit/map2/map_type_feldman_hashmap.h

index 20eab6b..6e8a3f0 100644 (file)
@@ -23,6 +23,9 @@ namespace cds { namespace container {
         template <typename T>
         using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
 
+        /// \p FeldmanHashMap level statistics
+        typedef cds::intrusive::feldman_hashset::level_statistics level_statistics;
+
         /// \p FeldmanHashMap traits
         struct traits
         {
index 2f31962..b321b7b 100644 (file)
@@ -29,6 +29,9 @@ namespace cds { namespace container {
         template <typename T>
         using bitwise_compare = cds::intrusive::feldman_hashset::bitwise_compare< T >;
 
+        /// \p FeldmanHashSet level statistics
+        typedef cds::intrusive::feldman_hashset::level_statistics level_statistics;
+
         /// \p FeldmanHashSet traits
         struct traits
         {
index 501766a..7ad23b8 100644 (file)
@@ -639,6 +639,14 @@ namespace cds { namespace container {
             return base_class::array_node_size();
         }
 
+        /// Collects tree level statistics into \p stat
+        /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
+        */
+        void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const
+        {
+            base_class::get_level_statistics(stat);
+        }
+
     public:
     ///@name Thread-safe iterators
         /** @anchor cds_container_FeldmanHashMap_rcu_iterators
index b8bbccf..d6b3bfa 100644 (file)
@@ -396,6 +396,14 @@ namespace cds { namespace container {
             return base_class::array_node_size();
         }
 
+        /// Collects tree level statistics into \p stat
+        /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
+        */
+        void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
+        {
+            base_class::get_level_statistics(stat);
+        }
+
     public:
         ///@name Thread-safe iterators
         /** @anchor cds_container_FeldmanHashSet_rcu_iterators
index 7fd1c14..2f8a03a 100644 (file)
@@ -78,7 +78,7 @@ namespace cds { namespace container {
         There are several specializations of \p %FeldmanHashMap for each \p GC. You should include:
         - <tt><cds/container/feldman_hashmap_hp.h></tt> for \p gc::HP garbage collector
         - <tt><cds/container/feldman_hashmap_dhp.h></tt> for \p gc::DHP garbage collector
-        - <tt><cds/container/feldman_hashmap_rcu.h></tt> for \ref cds_intrusive_FeldmanHashMap_rcu "RCU type". RCU specialization
+        - <tt><cds/container/feldman_hashmap_rcu.h></tt> for \ref cds_container_FeldmanHashMap_rcu "RCU type". RCU specialization
             has a slightly different interface.
     */
     template <
@@ -679,6 +679,14 @@ namespace cds { namespace container {
             return base_class::array_node_size();
         }
 
+        /// Collects tree level statistics into \p stat
+        /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
+        */
+        void get_level_statistics(std::vector< feldman_hashmap::level_statistics>& stat) const
+        {
+            base_class::get_level_statistics( stat );
+        }
+
     public:
     ///@name Thread-safe iterators
         /** @anchor cds_container_FeldmanHashMap_iterators
index 4e05f39..50462de 100644 (file)
@@ -437,6 +437,14 @@ namespace cds { namespace container {
             return base_class::array_node_size();
         }
 
+        /// Collects tree level statistics into \p stat
+        /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
+        */
+        void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
+        {
+            base_class::get_level_statistics(stat);
+        }
+
     public:
     ///@name Thread-safe iterators
         /** @anchor cds_container_FeldmanHashSet_iterators
index cb37cc2..e3bf8e4 100644 (file)
@@ -250,6 +250,26 @@ namespace cds { namespace intrusive {
             }
         };
 
+        /// One-level statistics, see \p FeldmanHashSet::get_level_statistics
+        struct level_statistics
+        {
+            size_t array_node_count;    ///< Count of array node at the level
+            size_t node_capacity;       ///< Array capacity
+
+            size_t data_cell_count;     ///< The number of data cells in all array node at this level
+            size_t array_cell_count;    ///< The number of array cells in all array node at this level
+            size_t empty_cell_count;    ///< The number of empty cells in all array node at this level
+
+            //@cond
+            level_statistics()
+                : array_node_count(0)
+                , data_cell_count(0)
+                , array_cell_count(0)
+                , empty_cell_count(0)
+            {}
+            //@endcond
+        };
+
         //@cond
         namespace details {
             template <typename HashType, typename UInt = size_t >
index 52e79b2..6eea7ed 100644 (file)
@@ -5,6 +5,7 @@
 
 #include <functional>   // std::ref
 #include <iterator>     // std::iterator_traits
+#include <vector>
 
 #include <cds/intrusive/details/feldman_hashset_base.h>
 #include <cds/details/allocator.h>
@@ -531,6 +532,15 @@ namespace cds { namespace intrusive {
             return m_Metrics.array_node_size;
         }
 
+        /// Collects tree level statistics into \p stat
+        /** @copydetails cds::intrusive::FeldmanHashSet::get_level_statistics
+        */
+        void get_level_statistics(std::vector<feldman_hashset::level_statistics>& stat) const
+        {
+            stat.clear();
+            gather_level_statistics(stat, 0, m_Head, head_size());
+        }
+
     protected:
         //@cond
         class iterator_base
@@ -1307,7 +1317,7 @@ namespace cds { namespace intrusive {
         void destroy_array_nodes(array_node * pArr, size_t nSize)
         {
             for (atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p) {
-                node_ptr slot = p->load(memory_model::memory_order_acquire);
+                node_ptr slot = p->load(memory_model::memory_order_relaxed);
                 if (slot.bits() == flag_array_node) {
                     destroy_array_nodes(to_array(slot.ptr()), array_node_size());
                     free_array_node(to_array(slot.ptr()));
@@ -1316,6 +1326,29 @@ namespace cds { namespace intrusive {
             }
         }
 
+        void gather_level_statistics(std::vector<feldman_hashset::level_statistics>& stat, size_t nLevel, array_node * pArr, size_t nSize) const
+        {
+            if (stat.size() <= nLevel) {
+                stat.resize(nLevel + 1);
+                stat[nLevel].node_capacity = nSize;
+            }
+
+            ++stat[nLevel].array_node_count;
+            for (atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p) {
+                node_ptr slot = p->load(memory_model::memory_order_relaxed);
+                if (slot.bits() == flag_array_node) {
+                    ++stat[nLevel].array_cell_count;
+                    gather_level_statistics(stat, nLevel + 1, to_array(slot.ptr()), array_node_size());
+                }
+                else if (slot.bits() == flag_array_converting)
+                    ++stat[nLevel].array_cell_count;
+                else if (slot.ptr())
+                    ++stat[nLevel].data_cell_count;
+                else
+                    ++stat[nLevel].empty_cell_count;
+            }
+        }
+
         void clear_array(array_node * pArrNode, size_t nSize)
         {
             back_off bkoff;
index fb713bb..3f2e460 100644 (file)
@@ -5,6 +5,7 @@
 
 #include <functional>   // std::ref
 #include <iterator>     // std::iterator_traits
+#include <vector>
 
 #include <cds/intrusive/details/feldman_hashset_base.h>
 #include <cds/details/allocator.h>
@@ -945,6 +946,21 @@ namespace cds { namespace intrusive {
             return m_Metrics.array_node_size;
         }
 
+        /// Collects tree level statistics into \p stat
+        /** @anchor cds_intrusive_FeldmanHashSet_hp_get_level_statistics
+            The function traverses the set and collects staistics for each level of the tree
+            into \p feldman_hashset::level_statistics struct. The element of \p stat[i]
+            represents statistics for level \p i, level 0 is head array.
+            The function is thread-safe and may be called in multi-threaded environment.
+
+            Result can be useful for estimating efficiency of hash functor you use.
+        */
+        void get_level_statistics(std::vector< feldman_hashset::level_statistics>& stat) const
+        {
+            stat.clear();
+            gather_level_statistics( stat, 0, m_Head, head_size() );
+        }
+
     public:
     ///@name Thread-safe iterators
         /** @anchor cds_intrusive_FeldmanHashSet_iterators
@@ -1101,8 +1117,8 @@ namespace cds { namespace intrusive {
 
         void destroy_array_nodes( array_node * pArr, size_t nSize )
         {
-            for ( atomic_node_ptr * p = pArr->nodes, *pLast = pArr->nodes + nSize; p != pLast; ++p ) {
-                node_ptr slot = p->load( memory_model::memory_order_acquire );
+            for ( atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p ) {
+                node_ptr slot = p->load( memory_model::memory_order_relaxed );
                 if ( slot.bits() == flag_array_node ) {
                     destroy_array_nodes(to_array(slot.ptr()), array_node_size());
                     free_array_node( to_array(slot.ptr()));
@@ -1111,6 +1127,28 @@ namespace cds { namespace intrusive {
             }
         }
 
+        void gather_level_statistics(std::vector<feldman_hashset::level_statistics>& stat, size_t nLevel, array_node * pArr, size_t nSize) const
+        {
+            if (stat.size() <= nLevel) {
+                stat.resize(nLevel + 1);
+                stat[nLevel].node_capacity = nSize;
+            }
+
+            ++stat[nLevel].array_node_count;
+            for (atomic_node_ptr * p = pArr->nodes, *pLast = p + nSize; p != pLast; ++p) {
+                node_ptr slot = p->load(memory_model::memory_order_relaxed);
+                if ( slot.bits()) {
+                    ++stat[nLevel].array_cell_count;
+                    if ( slot.bits() == flag_array_node )
+                        gather_level_statistics( stat, nLevel + 1, to_array(slot.ptr()), array_node_size());
+                }
+                else if ( slot.ptr())
+                    ++stat[nLevel].data_cell_count;
+                else
+                    ++stat[nLevel].empty_cell_count;
+            }
+        }
+
         void clear_array( array_node * pArrNode, size_t nSize )
         {
             back_off bkoff;
index e0e50ca..94382b4 100644 (file)
@@ -601,7 +601,7 @@ INPUT                  = $(DOXYPRJ_ROOT)/cds
 # into libc) for the transcoding. See http://www.gnu.org/software/libiconv for 
 # the list of possible encodings.
 
-INPUT_ENCODING         = windows-1251
+INPUT_ENCODING         = utf-8
 
 # If the value of the INPUT tag contains directories, you can use the 
 # FILE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp 
@@ -791,13 +791,13 @@ VERBATIM_HEADERS       = NO
 # of all compounds will be generated. Enable this if the project 
 # contains a lot of classes, structs, unions or interfaces.
 
-ALPHABETICAL_INDEX     = NO
+ALPHABETICAL_INDEX     = YES
 
 # If the alphabetical index is enabled (see ALPHABETICAL_INDEX) then 
 # the COLS_IN_ALPHA_INDEX tag can be used to specify the number of columns 
 # in which this list will be split (can be a number in the range [1..20])
 
-COLS_IN_ALPHA_INDEX    = 5
+COLS_IN_ALPHA_INDEX    = 2
 
 # In case all classes in a project start with a common prefix, all 
 # classes will be put under the same header in the alphabetical index. 
diff --git a/doxygen/image/feldman_hashset.png b/doxygen/image/feldman_hashset.png
new file mode 100644 (file)
index 0000000..63b213b
Binary files /dev/null and b/doxygen/image/feldman_hashset.png differ
diff --git a/doxygen/image/multilevel_hashset.png b/doxygen/image/multilevel_hashset.png
deleted file mode 100644 (file)
index 63b213b..0000000
Binary files a/doxygen/image/multilevel_hashset.png and /dev/null differ
diff --git a/install/description.txt b/install/description.txt
deleted file mode 100644 (file)
index 14beb95..0000000
+++ /dev/null
@@ -1 +0,0 @@
-ПК обработки измерительной информации НАП
\ No newline at end of file
diff --git a/install/post_install_script.sh b/install/post_install_script.sh
deleted file mode 100755 (executable)
index 0331eca..0000000
+++ /dev/null
@@ -1 +0,0 @@
-/usr/sbin/ldconfig
\ No newline at end of file
diff --git a/install/post_uninstall_script.sh b/install/post_uninstall_script.sh
deleted file mode 100755 (executable)
index 0331eca..0000000
+++ /dev/null
@@ -1 +0,0 @@
-/usr/sbin/ldconfig
\ No newline at end of file
index e3cc0b0..85935d0 100644 (file)
--- a/readme.md
+++ b/readme.md
@@ -39,6 +39,7 @@ See online doxygen-generated doc here: http://libcds.sourceforge.net/doc/cds-api
 - *integration* branch is intended for pull-request. Usually, *integration* branch is the same as *master*\r
 - *dev* branch is intended for main developing. Usually, it contains unstable code\r
 \r
+[![Project stats](https://www.openhub.net/p/khizmax-libcds/widgets/project_thin_badge.gif)](https://www.openhub.net/p/khizmax-libcds)\r
 \r
 References\r
 ----------\r
index 8d933e7..2642b09 100644 (file)
@@ -37,4 +37,10 @@ namespace map2 {
         shuffle( m_arrRemove.begin(), m_arrRemove.end() );
     }
 
+    void Map_DelOdd::endTestCase()
+    {
+        m_arrInsert.resize(0);
+        m_arrRemove.resize(0);
+    }
+
 } // namespace map2
index 9b39b8d..cee00c4 100644 (file)
@@ -11,12 +11,12 @@ namespace map2 {
     namespace {
         struct key_thread
         {
-            size_t  nKey;
-            size_t  nThread;
+            uint32_t  nKey;
+            uint32_t  nThread;
 
             key_thread( size_t key, size_t threadNo )
-                : nKey( key )
-                , nThread( threadNo )
+                : nKey( static_cast<uint32_t>(key))
+                , nThread( static_cast<uint32_t>(threadNo))
             {}
 
             key_thread()
@@ -708,6 +708,8 @@ namespace map2 {
                 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
             }
 
+            print_stat(testMap);
+
             check_before_cleanup( testMap );
 
             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
@@ -766,6 +768,7 @@ namespace map2 {
         }
 
         void setUpParams( const CppUnitMini::TestCfg& cfg );
+        virtual void endTestCase();
 
 #   include "map2/map_defs.h"
         CDSUNIT_DECLARE_MichaelMap
index ec1bbc2..b858846 100644 (file)
@@ -220,6 +220,21 @@ namespace map2 {
     static inline void print_stat( FeldmanHashMap< GC, K, T, Traits > const& m )
     {
         CPPUNIT_MSG( m.statistics() );
+
+        std::vector< cds::intrusive::feldman_hashset::level_statistics > level_stat;
+        m.get_level_statistics( level_stat );
+        CPPUNIT_MSG( "Level statistics, height=" << level_stat.size());
+        size_t i = 0;
+        CPPUNIT_MSG( "  i   node_count capacity    data_cell   array_cell   empty_cell" );
+        for (auto it = level_stat.begin(); it != level_stat.end(); ++it, ++i) {
+            CPPUNIT_MSG( std::setw(3)  << i                    << std::setw(0) << " "
+                      << std::setw(12) << it->array_node_count << std::setw(0) << " "
+                      << std::setw(8)  << it->node_capacity    << std::setw(0) << " "
+                      << std::setw(12) << it->data_cell_count  << std::setw(0) << " "
+                      << std::setw(12) << it->array_cell_count << std::setw(0) << " "
+                      << std::setw(12) << it->empty_cell_count << std::setw(0)
+                      );
+        }
     }
 
 }   // namespace map2