Adds a few single-threaded test cases for queue, stack, and set
authorPeizhao Ou <peizhaoo@uci.edu>
Fri, 15 Dec 2017 22:03:28 +0000 (14:03 -0800)
committerPeizhao Ou <peizhaoo@uci.edu>
Fri, 15 Dec 2017 22:03:28 +0000 (14:03 -0800)
87 files changed:
test/stress/CMakeLists.txt
test/stress/misc/common.h
test/stress/sequential/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3.h [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3_cuckoo.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3_ellentree.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3_feldman_hashset.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3_michael.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3_skip.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/del3/set_del3_split.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd.h [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd_cuckoo.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd_ellentree.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd_feldman_hashset.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd_michael.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd_skip.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/delodd/set_delodd_split.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind.h [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_cuckoo.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_ellentree_hp.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_ellentree_rcu.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_feldman_hashset_hp.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_feldman_hashset_rcu.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_michael_hp.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_michael_rcu.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_skip_hp.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_skip_rcu.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_split_hp.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_split_rcu.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_std.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_find/set_insdelfind_striped.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func.h [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func_cuckoo.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func_ellentree.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func_feldman_hashset.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func_michael.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func_skip.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func_split.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_func/set_insdel_func_striped.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string.h [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_cuckoo.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_ellentree.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_feldman_hashset.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_michael.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_skip.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_split.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_std.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/insdel_string/set_insdel_string_striped.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iter_erase/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/iter_erase/set_iter_erase.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iter_erase/set_iter_erase.h [new file with mode: 0644]
test/stress/sequential/sequential-set/iter_erase/set_iter_erase_feldman_hashset.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iter_erase/set_iter_erase_michael.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iter_erase/set_iter_erase_split.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iteration/CMakeLists.txt [new file with mode: 0644]
test/stress/sequential/sequential-set/iteration/set_iteration.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iteration/set_iteration.h [new file with mode: 0644]
test/stress/sequential/sequential-set/iteration/set_iteration_feldman_hashset.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iteration/set_iteration_michael.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/iteration/set_iteration_split.cpp [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_cuckoo.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_ellen_bintree.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_feldman_hashset.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_iterable_list.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_lazy_list.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_michael.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_michael_list.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_skip_list.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_split_list.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_std.h [new file with mode: 0644]
test/stress/sequential/sequential-set/set_type_striped.h [new file with mode: 0644]
test/stress/sequential/sequential_freelist_put_get.cpp [new file with mode: 0644]
test/stress/sequential/sequential_freelist_put_get_single.cpp [new file with mode: 0644]
test/stress/sequential/sequential_queue.cpp [new file with mode: 0644]
test/stress/sequential/sequential_stack.cpp [new file with mode: 0644]

index b733637..99d5dc1 100644 (file)
@@ -21,6 +21,7 @@ include_directories(
     ${CMAKE_CURRENT_SOURCE_DIR}
 )
 
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/sequential)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/misc)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/freelist)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/map)
index 09878f6..e297f16 100644 (file)
@@ -1,5 +1,5 @@
-#ifndef _COMMON_H
-#define _COMMON_H
+#ifndef _CDS_STRESS_TEST_COMMON_H
+#define _CDS_STRESS_TEST_COMMON_H
 
 #include <cds_test/stress_test.h>
 
@@ -7,4 +7,11 @@ typedef unsigned long long ullong;
 
 #define GetConfig(field) s_n##field = cfg.get_size_t(#field, s_n##field)
 
+
+#ifdef PERFORMANCE
+#define DEBUG(stmt)
+#else
+#define DEBUG(stmt) stmt
+#endif
+
 #endif
diff --git a/test/stress/sequential/CMakeLists.txt b/test/stress/sequential/CMakeLists.txt
new file mode 100644 (file)
index 0000000..3d09078
--- /dev/null
@@ -0,0 +1,26 @@
+set(PACKAGE_NAME stress-sequential)
+
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/sequential-set)
+
+set(CDSSTRESS_STACK_SOURCES
+    ../main.cpp
+    sequential_queue.cpp
+    sequential_freelist_put_get_single.cpp
+    sequential_freelist_put_get.cpp
+    sequential_stack.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_STACK_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
+
+add_custom_target( stress-sequential-all
+    DEPENDS
+        stress-sequential
+        stress-sequential-set
+)
diff --git a/test/stress/sequential/sequential-set/CMakeLists.txt b/test/stress/sequential/sequential-set/CMakeLists.txt
new file mode 100644 (file)
index 0000000..b3ac996
--- /dev/null
@@ -0,0 +1,21 @@
+
+set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DCDSUNIT_USE_URCU")
+
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/delodd)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/del3)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_find)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_func)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_string)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/iteration)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/iter_erase)
+
+add_custom_target( stress-sequential-set
+    DEPENDS
+        stress-sequential-set-delodd
+        stress-sequential-set-del3
+        stress-sequential-set-insdelfind
+        stress-sequential-set-insdel-func
+        stress-sequential-set-insdel-string
+        stress-sequential-set-iteration
+        stress-sequential-set-iter-erase
+)
diff --git a/test/stress/sequential/sequential-set/del3/CMakeLists.txt b/test/stress/sequential/sequential-set/del3/CMakeLists.txt
new file mode 100644 (file)
index 0000000..c27c42b
--- /dev/null
@@ -0,0 +1,22 @@
+set(PACKAGE_NAME stress-sequential-set-del3)
+
+set(CDSSTRESS_SET_DEL3_SOURCES
+    ../../../main.cpp
+    set_del3.cpp
+    set_del3_feldman_hashset.cpp
+    set_del3_cuckoo.cpp
+    set_del3_michael.cpp
+    set_del3_skip.cpp
+    set_del3_split.cpp
+    set_del3_ellentree.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_SET_DEL3_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
diff --git a/test/stress/sequential/sequential-set/del3/set_del3.cpp b/test/stress/sequential/sequential-set/del3/set_del3.cpp
new file mode 100644 (file)
index 0000000..4376fde
--- /dev/null
@@ -0,0 +1,155 @@
+/*
+    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.
+*/
+
+#include "set_del3.h"
+#include <string>
+
+namespace set {
+
+    size_t  Set_Del3::s_nSetSize = 1000000;
+    size_t  Set_Del3::s_nInsThreadCount = 4;
+    size_t  Set_Del3::s_nDelThreadCount = 4;
+    size_t  Set_Del3::s_nExtractThreadCount = 4;
+    size_t  Set_Del3::s_nFindThreadCount = 2;
+    size_t  Set_Del3::s_nMaxLoadFactor = 8;
+    size_t  Set_Del3::s_nPassCount = 100;
+    size_t  Set_Del3::s_nFeldmanPassCount = 100;
+    size_t  Set_Del3::s_nInsertPassCount = 1;
+    size_t  Set_Del3::s_nDeletePassCount = 1;
+    size_t  Set_Del3::s_nFindPassCount = 10;
+
+    size_t  Set_Del3::s_nCuckooInitialSize = 1024;
+    size_t  Set_Del3::s_nCuckooProbesetSize = 16;
+    size_t  Set_Del3::s_nCuckooProbesetThreshold = 0;
+
+    size_t Set_Del3::s_nFeldmanSet_HeadBits = 10;
+    size_t Set_Del3::s_nFeldmanSet_ArrayBits = 4;
+
+
+    size_t Set_Del3::s_nLoadFactor = 1;
+    std::vector<size_t> Set_Del3::m_arrData;
+
+    void Set_Del3::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "sequential_map_delodd" );
+
+        s_nSetSize = cfg.get_size_t( "MapSize", s_nSetSize );
+        if ( s_nSetSize < 1000 )
+            s_nSetSize = 1000;
+
+        s_nInsThreadCount = cfg.get_size_t( "InsThreadCount", s_nInsThreadCount );
+        if ( s_nInsThreadCount == 0 )
+            s_nInsThreadCount = 1;
+
+        s_nDelThreadCount = cfg.get_size_t( "DelThreadCount", s_nDelThreadCount );
+        s_nExtractThreadCount = cfg.get_size_t( "ExtractThreadCount", s_nExtractThreadCount );
+        s_nFindThreadCount = cfg.get_size_t( "FindThreadCount", s_nFindThreadCount );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        s_nPassCount = cfg.get_size_t("PassCount", s_nPassCount);
+        if (s_nPassCount == 0)
+          s_nPassCount = 100;
+
+        s_nFeldmanPassCount =
+            cfg.get_size_t("FeldmanPassCount", s_nFeldmanPassCount);
+        if (s_nFeldmanPassCount == 0)
+          s_nFeldmanPassCount = 500;
+
+        s_nInsertPassCount = cfg.get_size_t( "InsertPassCount", s_nInsertPassCount );
+        if ( s_nInsertPassCount == 0 )
+            s_nInsertPassCount = 1;
+
+        s_nDeletePassCount = cfg.get_size_t( "DeletePassCount", s_nDeletePassCount );
+        if ( s_nDeletePassCount == 0 )
+            s_nDeletePassCount = 1;
+
+        s_nFindPassCount = cfg.get_size_t( "FindPassCount", s_nFindPassCount );
+        if ( s_nFindPassCount == 0 )
+            s_nFindPassCount = 10;
+
+
+        s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+        if ( s_nCuckooInitialSize < 256 )
+            s_nCuckooInitialSize = 256;
+
+        s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+        if ( s_nCuckooProbesetSize < 8 )
+            s_nCuckooProbesetSize = 8;
+
+        s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+        s_nFeldmanSet_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanSet_HeadBits );
+        if ( s_nFeldmanSet_HeadBits == 0 )
+            s_nFeldmanSet_HeadBits = 2;
+
+        s_nFeldmanSet_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanSet_ArrayBits );
+        if ( s_nFeldmanSet_ArrayBits == 0 )
+            s_nFeldmanSet_ArrayBits = 2;
+
+        m_arrData.resize( s_nSetSize );
+        for ( size_t i = 0; i < s_nSetSize; ++i )
+            m_arrData[i] = i;
+        shuffle( m_arrData.begin(), m_arrData.end());
+    }
+
+    void Set_Del3::TearDownTestCase()
+    {
+        m_arrData.clear();
+    }
+
+    std::vector<size_t> Set_Del3_LF::get_load_factors()
+    {
+        cds_test::config const& cfg = get_config( "map_delodd" );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        std::vector<size_t> lf;
+        for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+            lf.push_back( n );
+
+        return lf;
+    }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+    static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+    {
+        return std::to_string( p.param );
+    }
+    INSTANTIATE_TEST_CASE_P( a, Set_Del3_LF, ::testing::ValuesIn( Set_Del3_LF::get_load_factors()), get_test_parameter_name );
+#else
+    INSTANTIATE_TEST_CASE_P( a, Set_Del3_LF, ::testing::ValuesIn( Set_Del3_LF::get_load_factors()));
+#endif
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/del3/set_del3.h b/test/stress/sequential/sequential-set/del3/set_del3.h
new file mode 100644 (file)
index 0000000..8a89c96
--- /dev/null
@@ -0,0 +1,868 @@
+/*
+    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.
+*/
+
+#include "../../../misc/common.h"
+#include "set_type.h"
+#include <cds/os/topology.h>
+#include <chrono>
+
+namespace set {
+
+    struct key_thread
+    {
+        uint32_t  nKey;
+        uint16_t  nThread;
+
+        key_thread( size_t key, size_t threadNo )
+            : nKey( static_cast<uint32_t>(key))
+            , nThread( static_cast<uint16_t>(threadNo))
+        {}
+
+        key_thread()
+            : nKey()
+            , nThread()
+        {}
+    };
+
+    static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
+
+    typedef set_type_base<key_thread, size_t>::key_val     key_value_pair;
+
+    template <>
+    struct cmp<key_thread> {
+        int operator ()(key_thread const& k1, key_thread const& k2) const
+        {
+            if ( k1.nKey < k2.nKey )
+                return -1;
+            if ( k1.nKey > k2.nKey )
+                return 1;
+            if ( k1.nThread < k2.nThread )
+                return -1;
+            if ( k1.nThread > k2.nThread )
+                return 1;
+            return 0;
+        }
+        int operator ()(key_thread const& k1, size_t k2) const
+        {
+            if ( k1.nKey < k2 )
+                return -1;
+            if ( k1.nKey > k2 )
+                return 1;
+            return 0;
+        }
+        int operator ()(size_t k1, key_thread const& k2) const
+        {
+            if ( k1 < k2.nKey )
+                return -1;
+            if ( k1 > k2.nKey )
+                return 1;
+            return 0;
+        }
+    };
+
+    template <>
+    struct less<set::key_thread>
+    {
+        bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
+        {
+            if ( k1.nKey <= k2.nKey )
+                return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
+            return false;
+        }
+    };
+
+    template <>
+    struct hash<set::key_thread>
+    {
+        typedef size_t             result_type;
+        typedef set::key_thread    argument_type;
+
+        size_t operator()( set::key_thread const& k ) const
+        {
+            return std::hash<size_t>()(k.nKey);
+        }
+
+        size_t operator()( size_t k ) const
+        {
+            return std::hash<size_t>()(k);
+        }
+    };
+
+
+    class Set_Del3: public cds_test::stress_fixture
+    {
+    public:
+        static size_t s_nSetSize;              // max set size
+        static size_t s_nInsThreadCount;       // insert thread count
+        static size_t s_nDelThreadCount;       // delete thread count
+        static size_t s_nExtractThreadCount;   // extract thread count
+        static size_t s_nMaxLoadFactor;        // maximum load factor
+        static size_t s_nPassCount;
+        static size_t s_nFeldmanPassCount;
+
+        static size_t s_nInsertPassCount;
+        static size_t s_nDeletePassCount;
+        static size_t s_nFindPassCount;
+        static size_t s_nFindThreadCount;      // find thread count
+
+        static size_t s_nCuckooInitialSize;    // initial size for CuckooSet
+        static size_t s_nCuckooProbesetSize;   // CuckooSet probeset size (only for list-based probeset)
+        static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
+
+        static size_t s_nFeldmanSet_HeadBits;
+        static size_t s_nFeldmanSet_ArrayBits;
+
+        static size_t s_nLoadFactor;
+
+        static std::vector<size_t> m_arrData;
+
+        static void SetUpTestCase();
+        static void TearDownTestCase();
+
+        template <typename Pred>
+        static void prepare_array( std::vector<size_t>& arr, Pred pred )
+        {
+            arr.reserve( m_arrData.size());
+            for ( auto el : m_arrData ) {
+                if ( pred( el ))
+                    arr.push_back( el );
+            }
+            arr.resize( arr.size());
+            shuffle( arr.begin(), arr.end());
+        }
+
+    protected:
+        typedef key_thread  key_type;
+        typedef size_t      value_type;
+
+        enum {
+            inserter_thread,
+            deleter_thread,
+            extractor_thread,
+            find_thread
+        };
+
+
+        // Inserts keys from [0..N)
+        template <class Set>
+        class Inserter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            struct update_functor
+            {
+                template <typename Q>
+                void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
+                {}
+
+                void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
+                {}
+            };
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t ) -> bool { return true; } );
+            }
+
+          public:
+            size_t  m_nInsertSuccess = 0;
+            size_t  m_nInsertFailed = 0;
+            size_t m_nInsertInitSuccess = 0;
+            size_t m_nInsertInitFailed = 0;
+
+            std::vector<size_t> m_arr;
+
+        public:
+          Inserter(cds_test::thread_pool &pool, Set &set)
+              : base_class(pool, inserter_thread), m_Set(set) {
+            init_data();
+          }
+
+          Inserter(Inserter &src) : base_class(src), m_Set(src.m_Set) {
+            init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Inserter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                for (size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass) {
+                  if (nPass & 1) {
+                    // insert pass
+                    for (auto el : m_arrData) {
+                      if (rSet.insert(key_type(el, 0)))
+                        ++m_nInsertSuccess;
+                      else
+                        ++m_nInsertFailed;
+                    }
+                  } else {
+                    // update pass
+                    for (auto el : m_arrData) {
+                      bool success;
+                      bool inserted;
+                      std::tie(success, inserted) =
+                          rSet.update(key_type(el, 0), update_functor());
+                      if (success && inserted)
+                        ++m_nInsertSuccess;
+                      else
+                        ++m_nInsertFailed;
+                    }
+                  }
+                }
+            }
+        };
+
+        struct key_equal {
+            bool operator()( key_type const& k1, key_type const& k2 ) const
+            {
+                return k1.nKey == k2.nKey;
+            }
+            bool operator()( size_t k1, key_type const& k2 ) const
+            {
+                return k1 == k2.nKey;
+            }
+            bool operator()( key_type const& k1, size_t k2 ) const
+            {
+                return k1.nKey == k2;
+            }
+            bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1.key, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, size_t k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( size_t k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+        };
+
+        struct key_less {
+            bool operator()( key_type const& k1, key_type const& k2 ) const
+            {
+                return k1.nKey < k2.nKey;
+            }
+            bool operator()( size_t k1, key_type const& k2 ) const
+            {
+                return k1 < k2.nKey;
+            }
+            bool operator()( key_type const& k1, size_t k2 ) const
+            {
+                return k1.nKey < k2;
+            }
+            bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1.key, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, size_t k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( size_t k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+
+            typedef key_equal   equal_to;
+        };
+
+        // Deletes odd keys from [0..N)
+        template <class Set>
+        class Deleter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+
+            std::vector<size_t> m_arr;
+
+        public:
+            Deleter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, deleter_thread )
+                , m_Set( set )
+            {}
+
+            Deleter( Deleter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Deleter( *this );
+            }
+
+            template <typename SetType, bool>
+            struct eraser {
+                static bool erase( SetType& s, size_t key, size_t /*thread*/)
+                {
+                    return s.erase_with( key, key_less());
+                }
+            };
+
+            template <typename SetType>
+            struct eraser<SetType, true> {
+                static bool erase(SetType& s, size_t key, size_t thread)
+                {
+                    return s.erase( key_type(key, thread));
+                }
+            };
+
+            virtual void test() {
+              Set &rSet = m_Set;
+              for (auto el : m_arrData) {
+                if (el & 3) {
+                  if (rSet.erase(key_type(el, 0)))
+                    ++m_nDeleteSuccess;
+                  else
+                    ++m_nDeleteFailed;
+                }
+              }
+            }
+        };
+
+        // Extracts odd keys from [0..N)
+        template <typename GC, class Set>
+        class Extractor: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            std::vector<size_t> m_arr;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nExtractSuccess = 0;
+            size_t  m_nExtractFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extractor_thread )
+                , m_Set( set )
+            {
+            }
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+            }
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test() {
+              Set &rSet = m_Set;
+              typename Set::guarded_ptr gp;
+
+              for (auto el : m_arrData) {
+                if (el & 3) {
+                  gp = rSet.extract(key_type(el, 0));
+                  if (gp)
+                    ++m_nExtractSuccess;
+                  else
+                    ++m_nExtractFailed;
+                  gp.release();
+                }
+              }
+            }
+        };
+
+        template <typename RCU, class Set>
+        class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+            std::vector<size_t> m_arr;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nExtractSuccess = 0;
+            size_t  m_nExtractFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extractor_thread )
+                , m_Set( set )
+            {}
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                typename Set::exempt_ptr xp;
+
+                Set_Del3& fixture = pool().template fixture<Set_Del3>();
+                size_t const nInsThreadCount = fixture.s_nInsThreadCount;
+
+                do {
+                    if ( id() & 1 ) {
+                        for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                            for ( auto el : m_arr ) {
+                                if ( Set::c_bExtractLockExternal ) {
+                                    typename Set::rcu_lock l;
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                else {
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                xp.release();
+                            }
+                        }
+                    }
+                    else {
+                        for ( auto el : m_arr ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( Set::c_bExtractLockExternal ) {
+                                    typename Set::rcu_lock l;
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                else {
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                xp.release();
+                            }
+                        }
+                    }
+                } while ( false );
+
+                m_arr.resize( 0 );
+            }
+        };
+
+        // Finds keys
+        template <class Set>
+        class Observer: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&                m_Set;
+
+        public:
+            size_t m_nFindEvenSuccess = 0;
+            size_t m_nFindEvenFailed = 0;
+            size_t m_nFindOddSuccess = 0;
+            size_t m_nFindOddFailed = 0;
+
+        public:
+            Observer( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, find_thread )
+                , m_Set( set )
+            {}
+
+            Observer( Observer& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Observer( *this );
+            }
+
+            virtual void test() {
+              Set &set = m_Set;
+              std::vector<size_t> const &arr = m_arrData;
+
+              for (size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass) {
+                for (size_t key : arr) {
+                  if (key & 3) {
+                    if (set.contains(key_thread(key, 0)))
+                      ++m_nFindOddSuccess;
+                    else
+                      ++m_nFindOddFailed;
+                  } else {
+                    // even keys MUST be in the map
+                    if (set.contains(key_thread(key, 0)))
+                      ++m_nFindEvenSuccess;
+                    else
+                      ++m_nFindEvenFailed;
+                  }
+                }
+              }
+            }
+        };
+
+    protected:
+        template <class Set>
+        void do_test_with( Set& testSet )
+        {
+            typedef Inserter<Set> insert_thread;
+            typedef Deleter<Set> delete_thread;
+            typedef Observer<Set> observer_thread;
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
+            pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
+            if ( s_nFindThreadCount )
+                pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+                << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+                << std::make_pair( "find_thread_count", s_nFindThreadCount )
+                << std::make_pair( "set_size", s_nSetSize )
+                << std::make_pair( "pass_count", s_nInsertPassCount );
+
+
+
+            size_t nInsertInitFailed = 0;
+            size_t nInsertInitSuccess = 0;
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+
+            size_t nFindEvenSuccess = 0;
+            size_t nFindEvenFailed = 0;
+            size_t nFindOddSuccess = 0;
+            size_t nFindOddFailed = 0;
+
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case inserter_thread:
+                    {
+                        insert_thread& inserter = static_cast<insert_thread&>(thr);
+                        nInsertSuccess += inserter.m_nInsertSuccess;
+                        nInsertFailed += inserter.m_nInsertFailed;
+                        nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+                        nInsertInitFailed += inserter.m_nInsertInitFailed;
+                    }
+                    break;
+                case deleter_thread:
+                    {
+                        delete_thread& deleter = static_cast<delete_thread&>(thr);
+                        nDeleteSuccess += deleter.m_nDeleteSuccess;
+                        nDeleteFailed += deleter.m_nDeleteFailed;
+                    }
+                    break;
+                case find_thread:
+                    {
+                        observer_thread& observer = static_cast<observer_thread&>( thr );
+                        nFindEvenSuccess = observer.m_nFindEvenSuccess;
+                        nFindEvenFailed = observer.m_nFindEvenFailed;
+                        nFindOddSuccess = observer.m_nFindOddSuccess;
+                        nFindOddFailed = observer.m_nFindOddFailed;
+                    }
+                    break;
+                default:
+                    assert( false );
+                }
+            }
+
+            size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
+
+            EXPECT_EQ( nInsertInitFailed, 0u );
+            EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
+            EXPECT_EQ( nFindEvenFailed, 0u );
+            EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
+            EXPECT_LE( nInsertSuccess, nDeleteSuccess );
+
+            propout()
+                << std::make_pair( "insert_init_success", nInsertInitSuccess )
+                << std::make_pair( "insert_init_failed", nInsertInitFailed )
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "find_even_success", nFindEvenSuccess )
+                << std::make_pair( "find_even_failed", nFindEvenFailed )
+                << std::make_pair( "find_odd_success", nFindOddSuccess )
+                << std::make_pair( "find_odd_failed", nFindOddFailed );
+        }
+
+        template <class Set>
+        void do_test_extract_with(Set &testSet, size_t pass_count) {
+          typedef Inserter<Set> insert_thread;
+          typedef Deleter<Set> delete_thread;
+          typedef Extractor<typename Set::gc, Set> extract_thread;
+          typedef Observer<Set> observer_thread;
+
+          size_t nInsertSuccess = 0;
+          size_t nInsertFailed = 0;
+          size_t nDeleteSuccess = 0;
+          size_t nDeleteFailed = 0;
+          size_t nExtractSuccess = 0;
+          size_t nExtractFailed = 0;
+          size_t nFindEvenSuccess = 0;
+          size_t nFindEvenFailed = 0;
+          size_t nFindOddSuccess = 0;
+          size_t nFindOddFailed = 0;
+
+          auto reset_stat = [&]() {
+            nInsertSuccess = 0;
+            nInsertFailed = 0;
+            nDeleteSuccess = 0;
+            nDeleteFailed = 0;
+            nExtractSuccess = 0;
+            nExtractFailed = 0;
+            nFindEvenSuccess = 0;
+            nFindEvenFailed = 0;
+            nFindOddSuccess = 0;
+            nFindOddFailed = 0;
+          };
+
+          auto insert_func = [&]() {
+            for (auto el : m_arrData) {
+              if (testSet.insert(key_type(el, 0)))
+                ++nInsertSuccess;
+              else
+                ++nInsertFailed;
+            }
+          };
+
+          auto delete_func = [&]() {
+            for (auto el : m_arrData) {
+              if (el & 3) {
+                if (testSet.erase(key_type(el, 0)))
+                  ++nDeleteSuccess;
+                else
+                  ++nDeleteFailed;
+              }
+            }
+          };
+
+          auto extract_func = [&]() {
+            for (auto el : m_arrData) {
+              if (el & 3) {
+                auto gp = testSet.extract(key_type(el, 0));
+                if (gp)
+                  ++nExtractSuccess;
+                else
+                  ++nExtractFailed;
+                gp.release();
+              }
+            }
+          };
+
+          auto find_func = [&]() {
+            for (size_t el : m_arrData) {
+              if (el & 3) {
+                if (testSet.contains(key_thread(el, 0)))
+                  ++nFindOddSuccess;
+                else
+                  ++nFindOddFailed;
+              } else {
+                // even keys MUST be in the map
+                if (testSet.contains(key_thread(el, 0)))
+                  ++nFindEvenSuccess;
+                else
+                  ++nFindEvenFailed;
+              }
+            }
+          };
+
+          auto test_func = [&](size_t count, std::function<void()> func) {
+            for (size_t i = 0; i < count; ++i) {
+              func();
+            }
+          };
+
+          size_t const nInitialOddKeys = s_nSetSize * 3 / 4;
+          size_t const nInitialEvenKeys = s_nSetSize / 4;
+          for (size_t nPass = 0; nPass < pass_count; ++nPass) {
+            // Start with an empty set.
+            testSet.clear();
+            reset_stat();
+
+            test_func(s_nInsertPassCount, insert_func);
+            EXPECT_EQ(nInsertSuccess, s_nSetSize);
+            reset_stat();
+
+            test_func(s_nFindPassCount, find_func);
+            EXPECT_EQ(nFindEvenFailed, 0u);
+            EXPECT_EQ(nFindOddFailed, 0u);
+            reset_stat();
+
+            test_func(s_nDeletePassCount, delete_func);
+            EXPECT_EQ(nDeleteSuccess, nInitialOddKeys);
+            reset_stat();
+
+            test_func(s_nInsertPassCount, insert_func);
+            EXPECT_EQ(nInsertSuccess, nInitialOddKeys);
+            reset_stat();
+
+            test_func(s_nDeletePassCount, extract_func);
+            EXPECT_EQ(nExtractSuccess, nInitialOddKeys);
+            reset_stat();
+
+            test_func(s_nFindPassCount, find_func);
+            EXPECT_EQ(nFindEvenFailed, 0u);
+            EXPECT_EQ(nFindOddSuccess, 0u);
+          }
+
+          //          std::chrono::duration<double> time_elapsed;
+          //          std::chrono::duration<double> time_diff;
+          //          std::chrono::time_point<std::chrono::steady_clock>
+          //          time_start;
+          //          std::chrono::time_point<std::chrono::steady_clock>
+          //          time_end;
+          //          time_start = std::chrono::steady_clock::now();
+          //          time_end = std::chrono::steady_clock::now();
+          //          time_diff = time_end - time_start;
+          //          time_elapsed = time_diff;
+          //          std::cout << "Time elapsed: " << time_elapsed.count() <<
+          //          "\n";
+        }
+
+        template <typename Set>
+        void analyze( Set& testSet )
+        {
+            // All even keys must be in the set
+            {
+                for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
+                    for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
+                        EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
+                    }
+                }
+            }
+
+            check_before_clear( testSet );
+
+            testSet.clear();
+            EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
+
+            additional_check( testSet );
+            print_stat( propout(), testSet );
+            additional_cleanup( testSet );
+        }
+
+        template <class Set>
+        void run_test()
+        {
+            static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
+
+            Set  testSet( *this );
+            do_test_with( testSet );
+            analyze( testSet );
+        }
+
+        template <class Set>
+        void run_test_extract(size_t pass_count = s_nPassCount)
+        {
+            static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
+
+            Set  testSet( *this );
+            do_test_extract_with( testSet, pass_count);
+        }
+
+        template <class Map>
+        void run_feldman();
+    };
+
+    class Set_Del3_LF: public Set_Del3
+        , public ::testing::WithParamInterface<size_t>
+    {
+    public:
+        template <class Set>
+        void run_test()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_Del3::run_test<Set>();
+        }
+
+        template <class Set>
+        void run_test_extract(size_t pass_count = s_nPassCount)
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_Del3::run_test_extract<Set>(pass_count);
+        }
+
+        static std::vector<size_t> get_load_factors();
+    };
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/del3/set_del3_cuckoo.cpp b/test/stress/sequential/sequential-set/del3/set_del3_cuckoo.cpp
new file mode 100644 (file)
index 0000000..4e9fb83
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_del3.h"
+#include "set_type_cuckoo.h"
+
+namespace set {
+
+    //CDSSTRESS_CuckooSet( Set_Del3, run_test, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/del3/set_del3_ellentree.cpp b/test/stress/sequential/sequential-set/del3/set_del3_ellentree.cpp
new file mode 100644 (file)
index 0000000..53e4f66
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_del3.h"
+#include "set_type_ellen_bintree.h"
+
+namespace set {
+
+    CDSSTRESS_EllenBinTreeSet( Set_Del3, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/del3/set_del3_feldman_hashset.cpp b/test/stress/sequential/sequential-set/del3/set_del3_feldman_hashset.cpp
new file mode 100644 (file)
index 0000000..1b05171
--- /dev/null
@@ -0,0 +1,50 @@
+/*
+    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.
+*/
+
+#include "set_del3.h"
+#include "set_type_feldman_hashset.h"
+
+namespace set {
+
+    template <class Set>
+    void Set_Del3::run_feldman()
+    {
+        typedef typename Set::traits original_traits;
+        struct traits: public original_traits {
+            enum { hash_size = sizeof( uint32_t ) + sizeof( uint16_t ) };
+        };
+        typedef typename Set::template rebind_traits< traits >::result set_type;
+
+        run_test_extract<set_type>(s_nFeldmanPassCount);
+    }
+
+    CDSSTRESS_FeldmanHashSet_fixed( Set_Del3, run_feldman, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/del3/set_del3_michael.cpp b/test/stress/sequential/sequential-set/del3/set_del3_michael.cpp
new file mode 100644 (file)
index 0000000..d7e64a0
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_del3.h"
+#include "set_type_michael.h"
+
+namespace set {
+
+    CDSSTRESS_MichaelSet( Set_Del3_LF, run_test_extract, key_thread, size_t )
+    CDSSTRESS_MichaelIterableSet( Set_Del3_LF, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/del3/set_del3_skip.cpp b/test/stress/sequential/sequential-set/del3/set_del3_skip.cpp
new file mode 100644 (file)
index 0000000..9767eeb
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_del3.h"
+#include "set_type_skip_list.h"
+
+namespace set {
+
+    CDSSTRESS_SkipListSet( Set_Del3, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/del3/set_del3_split.cpp b/test/stress/sequential/sequential-set/del3/set_del3_split.cpp
new file mode 100644 (file)
index 0000000..73e6833
--- /dev/null
@@ -0,0 +1,40 @@
+/*
+    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.
+*/
+
+#include "set_del3.h"
+#include "set_type_split_list.h"
+
+namespace set {
+
+    CDSSTRESS_SplitListSet( Set_Del3_LF, run_test_extract, key_thread, size_t )
+    CDSSTRESS_SplitListIterableSet( Set_Del3_LF, run_test_extract, key_thread, size_t )
+
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/CMakeLists.txt b/test/stress/sequential/sequential-set/delodd/CMakeLists.txt
new file mode 100644 (file)
index 0000000..06259bb
--- /dev/null
@@ -0,0 +1,22 @@
+set(PACKAGE_NAME stress-sequential-set-delodd)
+
+set(CDSSTRESS_SET_DELODD_SOURCES
+    ../../../main.cpp
+    set_delodd.cpp
+    set_delodd_cuckoo.cpp
+    set_delodd_ellentree.cpp
+    set_delodd_feldman_hashset.cpp
+    set_delodd_michael.cpp
+    set_delodd_skip.cpp
+    set_delodd_split.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_SET_DELODD_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd.cpp b/test/stress/sequential/sequential-set/delodd/set_delodd.cpp
new file mode 100644 (file)
index 0000000..f454f12
--- /dev/null
@@ -0,0 +1,131 @@
+/*
+    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.
+*/
+
+#include "set_delodd.h"
+
+namespace set {
+
+    size_t  Set_DelOdd::s_nSetSize = 1000000;
+    size_t  Set_DelOdd::s_nInsThreadCount = 4;
+    size_t  Set_DelOdd::s_nDelThreadCount = 4;
+    size_t  Set_DelOdd::s_nExtractThreadCount = 4;
+    size_t  Set_DelOdd::s_nFindThreadCount = 2;
+    size_t  Set_DelOdd::s_nMaxLoadFactor = 8;
+    size_t  Set_DelOdd::s_nInsertPassCount = 100;
+
+    size_t  Set_DelOdd::s_nCuckooInitialSize = 1024;
+    size_t  Set_DelOdd::s_nCuckooProbesetSize = 16;
+    size_t  Set_DelOdd::s_nCuckooProbesetThreshold = 0;
+
+    size_t Set_DelOdd::s_nFeldmanSet_HeadBits = 10;
+    size_t Set_DelOdd::s_nFeldmanSet_ArrayBits = 4;
+
+
+    size_t Set_DelOdd::s_nLoadFactor = 1;
+    std::vector<size_t> Set_DelOdd::m_arrData;
+
+    void Set_DelOdd::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "map_delodd" );
+
+        s_nSetSize = cfg.get_size_t( "MapSize", s_nSetSize );
+        if ( s_nSetSize < 1000 )
+            s_nSetSize = 1000;
+
+        s_nInsThreadCount = cfg.get_size_t( "InsThreadCount", s_nInsThreadCount );
+        if ( s_nInsThreadCount == 0 )
+            s_nInsThreadCount = 1;
+
+        s_nDelThreadCount = cfg.get_size_t( "DelThreadCount", s_nDelThreadCount );
+        s_nExtractThreadCount = cfg.get_size_t( "ExtractThreadCount", s_nExtractThreadCount );
+        s_nFindThreadCount = cfg.get_size_t( "FindThreadCount", s_nFindThreadCount );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        s_nInsertPassCount = cfg.get_size_t( "PassCount", s_nInsertPassCount );
+        if ( s_nInsertPassCount == 0 )
+            s_nInsertPassCount = 100;
+
+        s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+        if ( s_nCuckooInitialSize < 256 )
+            s_nCuckooInitialSize = 256;
+
+        s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+        if ( s_nCuckooProbesetSize < 8 )
+            s_nCuckooProbesetSize = 8;
+
+        s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+        s_nFeldmanSet_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanSet_HeadBits );
+        if ( s_nFeldmanSet_HeadBits == 0 )
+            s_nFeldmanSet_HeadBits = 2;
+
+        s_nFeldmanSet_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanSet_ArrayBits );
+        if ( s_nFeldmanSet_ArrayBits == 0 )
+            s_nFeldmanSet_ArrayBits = 2;
+
+        m_arrData.resize( s_nSetSize );
+        for ( size_t i = 0; i < s_nSetSize; ++i )
+            m_arrData[i] = i;
+        shuffle( m_arrData.begin(), m_arrData.end());
+    }
+
+    void Set_DelOdd::TearDownTestCase()
+    {
+        m_arrData.clear();
+    }
+
+    std::vector<size_t> Set_DelOdd_LF::get_load_factors()
+    {
+        cds_test::config const& cfg = get_config( "map_delodd" );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        std::vector<size_t> lf;
+        for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+            lf.push_back( n );
+
+        return lf;
+    }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+    static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+    {
+        return std::to_string( p.param );
+    }
+    INSTANTIATE_TEST_CASE_P( a, Set_DelOdd_LF, ::testing::ValuesIn( Set_DelOdd_LF::get_load_factors()), get_test_parameter_name );
+#else
+    INSTANTIATE_TEST_CASE_P( a, Set_DelOdd_LF, ::testing::ValuesIn( Set_DelOdd_LF::get_load_factors()));
+#endif
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd.h b/test/stress/sequential/sequential-set/delodd/set_delodd.h
new file mode 100644 (file)
index 0000000..45302cd
--- /dev/null
@@ -0,0 +1,921 @@
+/*
+    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.
+*/
+
+#include "set_type.h"
+#include <cds/os/topology.h>
+
+namespace set {
+
+    struct key_thread
+    {
+        uint32_t  nKey;
+        uint16_t  nThread;
+
+        key_thread( size_t key, size_t threadNo )
+            : nKey( static_cast<uint32_t>(key))
+            , nThread( static_cast<uint16_t>(threadNo))
+        {}
+
+        key_thread()
+            : nKey()
+            , nThread()
+        {}
+    };
+
+    static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
+
+    typedef set_type_base<key_thread, size_t>::key_val     key_value_pair;
+
+    template <>
+    struct cmp<key_thread> {
+        int operator ()(key_thread const& k1, key_thread const& k2) const
+        {
+            if ( k1.nKey < k2.nKey )
+                return -1;
+            if ( k1.nKey > k2.nKey )
+                return 1;
+            if ( k1.nThread < k2.nThread )
+                return -1;
+            if ( k1.nThread > k2.nThread )
+                return 1;
+            return 0;
+        }
+        int operator ()(key_thread const& k1, size_t k2) const
+        {
+            if ( k1.nKey < k2 )
+                return -1;
+            if ( k1.nKey > k2 )
+                return 1;
+            return 0;
+        }
+        int operator ()(size_t k1, key_thread const& k2) const
+        {
+            if ( k1 < k2.nKey )
+                return -1;
+            if ( k1 > k2.nKey )
+                return 1;
+            return 0;
+        }
+    };
+
+    template <>
+    struct less<set::key_thread>
+    {
+        bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
+        {
+            if ( k1.nKey <= k2.nKey )
+                return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
+            return false;
+        }
+    };
+
+    template <>
+    struct hash<set::key_thread>
+    {
+        typedef size_t             result_type;
+        typedef set::key_thread    argument_type;
+
+        size_t operator()( set::key_thread const& k ) const
+        {
+            return std::hash<size_t>()(k.nKey);
+        }
+
+        size_t operator()( size_t k ) const
+        {
+            return std::hash<size_t>()(k);
+        }
+    };
+
+
+    class Set_DelOdd: public cds_test::stress_fixture
+    {
+    public:
+        static size_t s_nSetSize;              // max set size
+        static size_t s_nInsThreadCount;       // insert thread count
+        static size_t s_nDelThreadCount;       // delete thread count
+        static size_t s_nExtractThreadCount;   // extract thread count
+        static size_t s_nMaxLoadFactor;        // maximum load factor
+        static size_t s_nInsertPassCount;
+        static size_t s_nFindThreadCount;      // find thread count
+
+        static size_t s_nCuckooInitialSize;    // initial size for CuckooSet
+        static size_t s_nCuckooProbesetSize;   // CuckooSet probeset size (only for list-based probeset)
+        static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
+
+        static size_t s_nFeldmanSet_HeadBits;
+        static size_t s_nFeldmanSet_ArrayBits;
+
+        static size_t s_nLoadFactor;
+
+        static std::vector<size_t> m_arrData;
+
+        static void SetUpTestCase();
+        static void TearDownTestCase();
+
+        template <typename Pred>
+        static void prepare_array( std::vector<size_t>& arr, Pred pred )
+        {
+            arr.reserve( m_arrData.size());
+            for ( auto el : m_arrData ) {
+                if ( pred( el ))
+                    arr.push_back( el );
+            }
+            arr.resize( arr.size());
+            shuffle( arr.begin(), arr.end());
+        }
+
+    protected:
+        typedef key_thread  key_type;
+        typedef size_t      value_type;
+
+        atomics::atomic<size_t> m_nInsThreadCount;
+
+        enum {
+            inserter_thread,
+            deleter_thread,
+            extractor_thread,
+            find_thread
+        };
+
+
+        // Inserts keys from [0..N)
+        template <class Set>
+        class Inserter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            struct update_functor
+            {
+                template <typename Q>
+                void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
+                {}
+
+                void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
+                {}
+            };
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t ) -> bool { return true; } );
+                for ( size_t i = 0; i < m_arr.size(); ++i ) {
+                    if ( m_Set.insert( key_type( m_arr[i], id())))
+                        ++m_nInsertInitSuccess;
+                    else
+                        ++m_nInsertInitFailed;
+                }
+            }
+
+        public:
+            size_t  m_nInsertSuccess = 0;
+            size_t  m_nInsertFailed = 0;
+            size_t m_nInsertInitSuccess = 0;
+            size_t m_nInsertInitFailed = 0;
+
+            std::vector<size_t> m_arr;
+
+        public:
+            Inserter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, inserter_thread )
+                , m_Set( set )
+            {
+                init_data();
+            }
+
+            Inserter( Inserter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Inserter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
+
+                for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
+                    if ( nPass & 1 ) {
+                        // insert pass
+                        for ( auto el : m_arr ) {
+                            if ( el & 1 ) {
+                                if ( rSet.insert( key_type( el, id())))
+                                    ++m_nInsertSuccess;
+                                else
+                                    ++m_nInsertFailed;
+                            }
+                        }
+                    }
+                    else {
+                        // update pass
+                        for ( auto el : m_arr ) {
+                            if ( el & 1 ) {
+                                bool success;
+                                bool inserted;
+                                std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
+                                if ( success && inserted )
+                                    ++m_nInsertSuccess;
+                                else
+                                    ++m_nInsertFailed;
+                            }
+                        }
+                    }
+                }
+
+                fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
+                m_arr.resize( 0 );
+            }
+        };
+
+        struct key_equal {
+            bool operator()( key_type const& k1, key_type const& k2 ) const
+            {
+                return k1.nKey == k2.nKey;
+            }
+            bool operator()( size_t k1, key_type const& k2 ) const
+            {
+                return k1 == k2.nKey;
+            }
+            bool operator()( key_type const& k1, size_t k2 ) const
+            {
+                return k1.nKey == k2;
+            }
+            bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1.key, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, size_t k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( size_t k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+        };
+
+        struct key_less {
+            bool operator()( key_type const& k1, key_type const& k2 ) const
+            {
+                return k1.nKey < k2.nKey;
+            }
+            bool operator()( size_t k1, key_type const& k2 ) const
+            {
+                return k1 < k2.nKey;
+            }
+            bool operator()( key_type const& k1, size_t k2 ) const
+            {
+                return k1.nKey < k2;
+            }
+            bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1.key, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, size_t k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( size_t k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+
+            typedef key_equal   equal_to;
+        };
+
+        // Deletes odd keys from [0..N)
+        template <class Set>
+        class Deleter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+
+            std::vector<size_t> m_arr;
+
+        public:
+            Deleter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, deleter_thread )
+                , m_Set( set )
+            {
+                init_data();
+            }
+            Deleter( Deleter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Deleter( *this );
+            }
+
+            template <typename SetType, bool>
+            struct eraser {
+                static bool erase( SetType& s, size_t key, size_t /*thread*/)
+                {
+                    return s.erase_with( key, key_less());
+                }
+            };
+
+            template <typename SetType>
+            struct eraser<SetType, true> {
+                static bool erase(SetType& s, size_t key, size_t thread)
+                {
+                    return s.erase( key_type(key, thread));
+                }
+            };
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                size_t const nInsThreadCount = s_nInsThreadCount;
+                Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
+
+                do {
+                    if ( id() & 1 ) {
+                        for ( auto el : m_arr ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( rSet.erase( key_type( el, k )))
+                                    ++m_nDeleteSuccess;
+                                else
+                                    ++m_nDeleteFailed;
+                            }
+                        }
+                    }
+                    else {
+                        for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                            for ( auto el : m_arr ) {
+                                if ( rSet.erase( key_type( el, k )))
+                                    ++m_nDeleteSuccess;
+                                else
+                                    ++m_nDeleteFailed;
+                            }
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+                m_arr.resize( 0 );
+            }
+        };
+
+        // Extracts odd keys from [0..N)
+        template <typename GC, class Set>
+        class Extractor: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            std::vector<size_t> m_arr;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nExtractSuccess = 0;
+            size_t  m_nExtractFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extractor_thread )
+                , m_Set( set )
+            {
+                init_data();
+            }
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                typename Set::guarded_ptr gp;
+
+                Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
+                size_t const nInsThreadCount = s_nInsThreadCount;
+
+                do {
+                    if ( id() & 1 ) {
+                        for ( auto el : m_arr ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                gp = rSet.extract( key_type( el, k ));
+                                if ( gp )
+                                    ++m_nExtractSuccess;
+                                else
+                                    ++m_nExtractFailed;
+                                gp.release();
+                            }
+                        }
+                    }
+                    else {
+                        for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                            for ( auto el : m_arr ) {
+                                gp = rSet.extract( key_type( el, k ));
+                                if ( gp )
+                                    ++m_nExtractSuccess;
+                                else
+                                    ++m_nExtractFailed;
+                                gp.release();
+                            }
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+                m_arr.resize( 0 );
+            }
+        };
+
+        template <typename RCU, class Set>
+        class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+            std::vector<size_t> m_arr;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nExtractSuccess = 0;
+            size_t  m_nExtractFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extractor_thread )
+                , m_Set( set )
+            {
+                init_data();
+            }
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                typename Set::exempt_ptr xp;
+
+                Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
+                size_t const nInsThreadCount = fixture.s_nInsThreadCount;
+
+                do {
+                    if ( id() & 1 ) {
+                        for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                            for ( auto el : m_arr ) {
+                                if ( Set::c_bExtractLockExternal ) {
+                                    typename Set::rcu_lock l;
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                else {
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                xp.release();
+                            }
+                        }
+                    }
+                    else {
+                        for ( auto el : m_arr ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( Set::c_bExtractLockExternal ) {
+                                    typename Set::rcu_lock l;
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                else {
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                xp.release();
+                            }
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+                m_arr.resize( 0 );
+            }
+        };
+
+        // Finds keys
+        template <class Set>
+        class Observer: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&                m_Set;
+
+        public:
+            size_t m_nFindEvenSuccess = 0;
+            size_t m_nFindEvenFailed = 0;
+            size_t m_nFindOddSuccess = 0;
+            size_t m_nFindOddFailed = 0;
+
+        public:
+            Observer( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, find_thread )
+                , m_Set( set )
+            {}
+
+            Observer( Observer& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Observer( *this );
+            }
+
+            virtual void test()
+            {
+                Set& set = m_Set;
+                Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
+                std::vector<size_t> const& arr = m_arrData;
+                size_t const nInsThreadCount = s_nInsThreadCount;
+
+                do {
+                    for ( size_t key : arr ) {
+                        if ( key & 1 ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( set.contains( key_thread( key, k )))
+                                    ++m_nFindOddSuccess;
+                                else
+                                    ++m_nFindOddFailed;
+                            }
+                        }
+                        else {
+                            // even keys MUST be in the map
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( set.contains( key_thread( key, k )))
+                                    ++m_nFindEvenSuccess;
+                                else
+                                    ++m_nFindEvenFailed;
+                            }
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+            }
+        };
+
+    protected:
+        template <class Set>
+        void do_test_with( Set& testSet )
+        {
+            typedef Inserter<Set> insert_thread;
+            typedef Deleter<Set> delete_thread;
+            typedef Observer<Set> observer_thread;
+
+            m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
+            pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
+            if ( s_nFindThreadCount )
+                pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+                << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+                << std::make_pair( "find_thread_count", s_nFindThreadCount )
+                << std::make_pair( "set_size", s_nSetSize )
+                << std::make_pair( "pass_count", s_nInsertPassCount );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertInitFailed = 0;
+            size_t nInsertInitSuccess = 0;
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+
+            size_t nFindEvenSuccess = 0;
+            size_t nFindEvenFailed = 0;
+            size_t nFindOddSuccess = 0;
+            size_t nFindOddFailed = 0;
+
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case inserter_thread:
+                    {
+                        insert_thread& inserter = static_cast<insert_thread&>(thr);
+                        nInsertSuccess += inserter.m_nInsertSuccess;
+                        nInsertFailed += inserter.m_nInsertFailed;
+                        nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+                        nInsertInitFailed += inserter.m_nInsertInitFailed;
+                    }
+                    break;
+                case deleter_thread:
+                    {
+                        delete_thread& deleter = static_cast<delete_thread&>(thr);
+                        nDeleteSuccess += deleter.m_nDeleteSuccess;
+                        nDeleteFailed += deleter.m_nDeleteFailed;
+                    }
+                    break;
+                case find_thread:
+                    {
+                        observer_thread& observer = static_cast<observer_thread&>( thr );
+                        nFindEvenSuccess = observer.m_nFindEvenSuccess;
+                        nFindEvenFailed = observer.m_nFindEvenFailed;
+                        nFindOddSuccess = observer.m_nFindOddSuccess;
+                        nFindOddFailed = observer.m_nFindOddFailed;
+                    }
+                    break;
+                default:
+                    assert( false );
+                }
+            }
+
+            size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
+
+            EXPECT_EQ( nInsertInitFailed, 0u );
+            EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
+            EXPECT_EQ( nFindEvenFailed, 0u );
+            EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
+            EXPECT_LE( nInsertSuccess, nDeleteSuccess );
+
+            propout()
+                << std::make_pair( "insert_init_success", nInsertInitSuccess )
+                << std::make_pair( "insert_init_failed", nInsertInitFailed )
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "find_even_success", nFindEvenSuccess )
+                << std::make_pair( "find_even_failed", nFindEvenFailed )
+                << std::make_pair( "find_odd_success", nFindOddSuccess )
+                << std::make_pair( "find_odd_failed", nFindOddFailed );
+        }
+
+        template <class Set>
+        void do_test_extract_with( Set& testSet )
+        {
+            typedef Inserter<Set> insert_thread;
+            typedef Deleter<Set> delete_thread;
+            typedef Extractor< typename Set::gc, Set > extract_thread;
+            typedef Observer<Set> observer_thread;
+
+            m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
+            if ( s_nDelThreadCount )
+                pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
+            if ( s_nExtractThreadCount )
+                pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
+            if ( s_nFindThreadCount )
+                pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+                << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+                << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
+                << std::make_pair( "find_thread_count", s_nFindThreadCount )
+                << std::make_pair( "set_size", s_nSetSize )
+                << std::make_pair( "pass_count", s_nInsertPassCount );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertInitFailed = 0;
+            size_t nInsertInitSuccess = 0;
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+            size_t nExtractSuccess = 0;
+            size_t nExtractFailed = 0;
+
+            size_t nFindEvenSuccess = 0;
+            size_t nFindEvenFailed = 0;
+            size_t nFindOddSuccess = 0;
+            size_t nFindOddFailed = 0;
+
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case inserter_thread:
+                    {
+                        insert_thread& inserter = static_cast<insert_thread&>( thr );
+                        nInsertSuccess += inserter.m_nInsertSuccess;
+                        nInsertFailed += inserter.m_nInsertFailed;
+                        nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+                        nInsertInitFailed += inserter.m_nInsertInitFailed;
+                    }
+                    break;
+                case deleter_thread:
+                    {
+                        delete_thread& deleter = static_cast<delete_thread&>(thr);
+                        nDeleteSuccess += deleter.m_nDeleteSuccess;
+                        nDeleteFailed += deleter.m_nDeleteFailed;
+                    }
+                    break;
+                case extractor_thread:
+                    {
+                        extract_thread& extractor = static_cast<extract_thread&>(thr);
+                        nExtractSuccess += extractor.m_nExtractSuccess;
+                        nExtractFailed += extractor.m_nExtractFailed;
+                    }
+                    break;
+                case find_thread:
+                    {
+                        observer_thread& observer = static_cast<observer_thread&>( thr );
+                        nFindEvenSuccess = observer.m_nFindEvenSuccess;
+                        nFindEvenFailed = observer.m_nFindEvenFailed;
+                        nFindOddSuccess = observer.m_nFindOddSuccess;
+                        nFindOddFailed = observer.m_nFindOddFailed;
+                    }
+                    break;
+                default:
+                    assert( false );
+                }
+            }
+
+            size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
+
+            EXPECT_EQ( nInsertInitFailed, 0u );
+            EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
+            EXPECT_EQ( nFindEvenFailed, 0u );
+            EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
+            EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
+
+            propout()
+                << std::make_pair( "insert_init_success", nInsertInitSuccess )
+                << std::make_pair( "insert_init_failed", nInsertInitFailed )
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "extract_success", nExtractSuccess )
+                << std::make_pair( "extract_failed", nExtractFailed )
+                << std::make_pair( "find_even_success", nFindEvenSuccess )
+                << std::make_pair( "find_even_failed", nFindEvenFailed )
+                << std::make_pair( "find_odd_success", nFindOddSuccess )
+                << std::make_pair( "find_odd_failed", nFindOddFailed );
+        }
+
+        template <typename Set>
+        void analyze( Set& testSet )
+        {
+            // All even keys must be in the set
+            {
+                for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
+                    for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
+                        EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
+                    }
+                }
+            }
+
+            check_before_clear( testSet );
+
+            testSet.clear();
+            EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
+
+            additional_check( testSet );
+            print_stat( propout(), testSet );
+            additional_cleanup( testSet );
+        }
+
+        template <class Set>
+        void run_test()
+        {
+            static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
+
+            Set  testSet( *this );
+            do_test_with( testSet );
+            analyze( testSet );
+        }
+
+        template <class Set>
+        void run_test_extract()
+        {
+            static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
+
+            Set  testSet( *this );
+            do_test_extract_with( testSet );
+            analyze( testSet );
+        }
+
+        template <class Map>
+        void run_feldman();
+    };
+
+    class Set_DelOdd_LF: public Set_DelOdd
+        , public ::testing::WithParamInterface<size_t>
+    {
+    public:
+        template <class Set>
+        void run_test()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_DelOdd::run_test<Set>();
+        }
+
+        template <class Set>
+        void run_test_extract()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_DelOdd::run_test_extract<Set>();
+        }
+
+        static std::vector<size_t> get_load_factors();
+    };
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd_cuckoo.cpp b/test/stress/sequential/sequential-set/delodd/set_delodd_cuckoo.cpp
new file mode 100644 (file)
index 0000000..ceefac6
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_delodd.h"
+#include "set_type_cuckoo.h"
+
+namespace set {
+
+    //CDSSTRESS_CuckooSet( Set_DelOdd, run_test, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd_ellentree.cpp b/test/stress/sequential/sequential-set/delodd/set_delodd_ellentree.cpp
new file mode 100644 (file)
index 0000000..49dbfff
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_delodd.h"
+#include "set_type_ellen_bintree.h"
+
+namespace set {
+
+    CDSSTRESS_EllenBinTreeSet( Set_DelOdd, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd_feldman_hashset.cpp b/test/stress/sequential/sequential-set/delodd/set_delodd_feldman_hashset.cpp
new file mode 100644 (file)
index 0000000..41a2dd4
--- /dev/null
@@ -0,0 +1,50 @@
+/*
+    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.
+*/
+
+#include "set_delodd.h"
+#include "set_type_feldman_hashset.h"
+
+namespace set {
+
+    template <class Set>
+    void Set_DelOdd::run_feldman()
+    {
+        typedef typename Set::traits original_traits;
+        struct traits: public original_traits {
+            enum { hash_size = sizeof( uint32_t ) + sizeof( uint16_t ) };
+        };
+        typedef typename Set::template rebind_traits< traits >::result set_type;
+
+        run_test_extract<set_type>();
+    }
+
+    CDSSTRESS_FeldmanHashSet_fixed( Set_DelOdd, run_feldman, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd_michael.cpp b/test/stress/sequential/sequential-set/delodd/set_delodd_michael.cpp
new file mode 100644 (file)
index 0000000..f41c015
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_delodd.h"
+#include "set_type_michael.h"
+
+namespace set {
+
+    CDSSTRESS_MichaelSet( Set_DelOdd_LF, run_test_extract, key_thread, size_t )
+    CDSSTRESS_MichaelIterableSet( Set_DelOdd_LF, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd_skip.cpp b/test/stress/sequential/sequential-set/delodd/set_delodd_skip.cpp
new file mode 100644 (file)
index 0000000..f5014ef
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_delodd.h"
+#include "set_type_skip_list.h"
+
+namespace set {
+
+    CDSSTRESS_SkipListSet( Set_DelOdd, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/delodd/set_delodd_split.cpp b/test/stress/sequential/sequential-set/delodd/set_delodd_split.cpp
new file mode 100644 (file)
index 0000000..ce08ba4
--- /dev/null
@@ -0,0 +1,40 @@
+/*
+    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.
+*/
+
+#include "set_delodd.h"
+#include "set_type_split_list.h"
+
+namespace set {
+
+    CDSSTRESS_SplitListSet( Set_DelOdd_LF, run_test_extract, key_thread, size_t )
+    CDSSTRESS_SplitListIterableSet( Set_DelOdd_LF, run_test_extract, key_thread, size_t )
+
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/CMakeLists.txt b/test/stress/sequential/sequential-set/insdel_find/CMakeLists.txt
new file mode 100644 (file)
index 0000000..eb3ef45
--- /dev/null
@@ -0,0 +1,56 @@
+set(EXE_SET_INSDELFIND_HP stress-sequential-set-insdelfind-hp)
+set(EXE_SET_INSDELFIND_RCU stress-sequential-set-insdelfind-rcu)
+set(EXE_SET_INSDELFIND_LOCK stress-sequential-set-insdelfind-lock)
+
+set(CDSSTRESS_SET_INSDELFIND_HP_SOURCES
+    ../../../main.cpp
+    set_insdelfind.cpp
+    set_insdelfind_ellentree_hp.cpp
+    set_insdelfind_feldman_hashset_hp.cpp
+    set_insdelfind_michael_hp.cpp
+    set_insdelfind_skip_hp.cpp
+    set_insdelfind_split_hp.cpp
+)
+
+set(CDSSTRESS_SET_INSDELFIND_RCU_SOURCES
+    ../../../main.cpp
+    set_insdelfind.cpp
+    set_insdelfind_ellentree_rcu.cpp
+    set_insdelfind_feldman_hashset_rcu.cpp
+    set_insdelfind_michael_rcu.cpp
+    set_insdelfind_skip_rcu.cpp
+    set_insdelfind_split_rcu.cpp
+)
+
+set(CDSSTRESS_SET_INSDELFIND_LOCK_SOURCES
+    ../../../main.cpp
+    set_insdelfind.cpp
+    set_insdelfind_cuckoo.cpp
+    set_insdelfind_std.cpp
+    set_insdelfind_striped.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${EXE_SET_INSDELFIND_HP} ${CDSSTRESS_SET_INSDELFIND_HP_SOURCES})
+target_link_libraries(${EXE_SET_INSDELFIND_HP} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+add_test(NAME ${EXE_SET_INSDELFIND_HP} COMMAND ${EXE_SET_INSDELFIND_HP} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
+
+add_executable(${EXE_SET_INSDELFIND_RCU} ${CDSSTRESS_SET_INSDELFIND_RCU_SOURCES})
+target_link_libraries(${EXE_SET_INSDELFIND_RCU} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+add_test(NAME ${EXE_SET_INSDELFIND_RCU} COMMAND ${EXE_SET_INSDELFIND_RCU} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
+
+add_executable(${EXE_SET_INSDELFIND_LOCK} ${CDSSTRESS_SET_INSDELFIND_LOCK_SOURCES})
+target_link_libraries(${EXE_SET_INSDELFIND_LOCK} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+add_test(NAME ${EXE_SET_INSDELFIND_LOCK} COMMAND ${EXE_SET_INSDELFIND_LOCK} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
+
+add_custom_target( stress-sequential-set-insdelfind
+    DEPENDS
+        stress-sequential-set-insdelfind-hp
+        stress-sequential-set-insdelfind-rcu
+        stress-sequential-set-insdelfind-lock
+)
+
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind.cpp
new file mode 100644 (file)
index 0000000..afcff02
--- /dev/null
@@ -0,0 +1,136 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+
+namespace set {
+
+    size_t Set_InsDelFind::s_nSetSize = 500000;      // initial set size
+    size_t Set_InsDelFind::s_nThreadCount = 8;       // thread count
+    size_t Set_InsDelFind::s_nMaxLoadFactor = 8;     // maximum load factor
+    unsigned int Set_InsDelFind::s_nInsertPercentage = 5;
+    unsigned int Set_InsDelFind::s_nDeletePercentage = 5;
+    unsigned int Set_InsDelFind::s_nDuration = 30;   // test duration, seconds
+
+    size_t Set_InsDelFind::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+    size_t Set_InsDelFind::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+    size_t Set_InsDelFind::s_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+    size_t Set_InsDelFind::s_nFeldmanSet_HeadBits = 10;
+    size_t Set_InsDelFind::s_nFeldmanSet_ArrayBits = 4;
+
+    size_t Set_InsDelFind::s_nLoadFactor = 2;
+    Set_InsDelFind::actions Set_InsDelFind::s_arrShuffle[Set_InsDelFind::c_nShuffleSize];
+
+    void Set_InsDelFind::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "map_insdelfind" );
+
+        s_nSetSize = cfg.get_size_t( "InitialMapSize", s_nSetSize );
+        if ( s_nSetSize < 1000 )
+            s_nSetSize = 1000;
+
+        s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
+        if ( s_nThreadCount == 0 )
+            s_nThreadCount = 2;
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        s_nInsertPercentage = cfg.get_uint( "InsertPercentage", s_nInsertPercentage );
+        if ( s_nInsertPercentage == 0 || s_nInsertPercentage > 90 )
+            s_nInsertPercentage = 5;
+
+        s_nDeletePercentage = cfg.get_uint( "DeletePercentage", s_nDeletePercentage );
+        if ( s_nDeletePercentage == 0 || s_nDeletePercentage > 90 )
+            s_nDeletePercentage = 5;
+
+        s_nDuration = cfg.get_uint( "Duration", s_nDuration );
+        if ( s_nDuration == 0 )
+            s_nDuration = 5;
+
+        s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+        if ( s_nCuckooInitialSize < 256 )
+            s_nCuckooInitialSize = 256;
+
+        s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+        if ( s_nCuckooProbesetSize < 8 )
+            s_nCuckooProbesetSize = 8;
+
+        s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+        s_nFeldmanSet_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanSet_HeadBits );
+        if ( s_nFeldmanSet_HeadBits == 0 )
+            s_nFeldmanSet_HeadBits = 2;
+
+        s_nFeldmanSet_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanSet_ArrayBits );
+        if ( s_nFeldmanSet_ArrayBits == 0 )
+            s_nFeldmanSet_ArrayBits = 2;
+
+        actions * pFirst = s_arrShuffle;
+        actions * pLast = s_arrShuffle + s_nInsertPercentage;
+        std::fill( pFirst, pLast, do_insert );
+        pFirst = pLast;
+        pLast += s_nDeletePercentage;
+        std::fill( pFirst, pLast, do_delete );
+        pFirst = pLast;
+        pLast = s_arrShuffle + sizeof( s_arrShuffle ) / sizeof( s_arrShuffle[0] );
+        if ( pFirst < pLast )
+            std::fill( pFirst, pLast, do_find );
+        shuffle( s_arrShuffle, pLast );
+    }
+
+    std::vector<size_t> Set_InsDelFind_LF::get_load_factors()
+    {
+        cds_test::config const& cfg = get_config( "map_delodd" );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        std::vector<size_t> lf;
+        for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+            lf.push_back( n );
+
+        return lf;
+    }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+    static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+    {
+        return std::to_string( p.param );
+    }
+    INSTANTIATE_TEST_CASE_P( a, Set_InsDelFind_LF, ::testing::ValuesIn( Set_InsDelFind_LF::get_load_factors()), get_test_parameter_name );
+#else
+    INSTANTIATE_TEST_CASE_P( a, Set_InsDelFind_LF, ::testing::ValuesIn( Set_InsDelFind_LF::get_load_factors()));
+#endif
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind.h b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind.h
new file mode 100644 (file)
index 0000000..c28ab90
--- /dev/null
@@ -0,0 +1,233 @@
+/*
+    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.
+*/
+
+#include "set_type.h"
+
+namespace set {
+
+    class Set_InsDelFind: public cds_test::stress_fixture
+    {
+    public:
+        static size_t s_nSetSize;           // initial set size
+        static size_t s_nThreadCount;       // thread count
+        static size_t s_nMaxLoadFactor;     // maximum load factor
+        static unsigned int s_nInsertPercentage;
+        static unsigned int s_nDeletePercentage;
+        static unsigned int s_nDuration;   // test duration, seconds
+
+        static size_t  s_nCuckooInitialSize;        // initial size for CuckooSet
+        static size_t  s_nCuckooProbesetSize;       // CuckooSet probeset size (only for list-based probeset)
+        static size_t  s_nCuckooProbesetThreshold;  // CUckooSet probeset threshold (0 - use default)
+
+        static size_t s_nFeldmanSet_HeadBits;
+        static size_t s_nFeldmanSet_ArrayBits;
+
+        static size_t s_nLoadFactor;
+
+        static void SetUpTestCase();
+        //static void TearDownTestCase();
+
+    public:
+        enum actions
+        {
+            do_find,
+            do_insert,
+            do_delete
+        };
+        static const unsigned int c_nShuffleSize = 100;
+        static actions s_arrShuffle[c_nShuffleSize];
+
+    protected:
+        typedef size_t  key_type;
+        typedef size_t  value_type;
+
+        template <class Set>
+        class Worker: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+        public:
+            size_t  m_nInsertSuccess = 0;
+            size_t  m_nInsertFailed = 0;
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+            size_t  m_nFindSuccess = 0;
+            size_t  m_nFindFailed = 0;
+
+        public:
+            Worker( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool )
+                , m_Set( set )
+            {}
+
+            Worker( Worker& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Worker( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                Set_InsDelFind& fixture = pool().template fixture<Set_InsDelFind>();
+
+                unsigned int i = 0;
+                size_t const nNormalize = size_t(-1) / ( fixture.s_nSetSize * 2);
+
+                size_t nRand = 0;
+                while ( !time_elapsed()) {
+                    nRand = cds::bitop::RandXorShift(nRand);
+                    size_t n = nRand / nNormalize;
+                    switch ( s_arrShuffle[i] ) {
+                    case do_find:
+                        if ( rSet.contains( n ))
+                            ++m_nFindSuccess;
+                        else
+                            ++m_nFindFailed;
+                        break;
+                    case do_insert:
+                        if ( rSet.insert( n ))
+                            ++m_nInsertSuccess;
+                        else
+                            ++m_nInsertFailed;
+                        break;
+                    case do_delete:
+                        if ( rSet.erase( n ))
+                            ++m_nDeleteSuccess;
+                        else
+                            ++m_nDeleteFailed;
+                        break;
+                    }
+
+                    if ( ++i >= c_nShuffleSize )
+                        i = 0;
+                }
+            }
+        };
+
+    protected:
+        template <class Set>
+        void do_test( Set& testSet )
+        {
+            typedef Worker<Set> work_thread;
+
+            // fill map - only odd number
+            {
+                size_t * pInitArr = new size_t[ s_nSetSize ];
+                size_t * pEnd = pInitArr + s_nSetSize;
+                for ( size_t i = 0; i < s_nSetSize; ++i )
+                    pInitArr[i] = i * 2 + 1;
+                shuffle( pInitArr, pEnd );
+                for ( size_t * p = pInitArr; p < pEnd; ++p )
+                    testSet.insert( typename Set::value_type( *p, *p ));
+                delete [] pInitArr;
+            }
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new work_thread( pool, testSet ), s_nThreadCount );
+
+            propout() << std::make_pair( "thread_count", s_nThreadCount )
+                << std::make_pair( "set_size", s_nSetSize )
+                << std::make_pair( "insert_percentage", s_nInsertPercentage )
+                << std::make_pair( "delete_percentage", s_nDeletePercentage )
+                << std::make_pair( "total_duration", s_nDuration );
+
+            std::chrono::milliseconds duration = pool.run( std::chrono::seconds( s_nDuration ));
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+            size_t nFindSuccess = 0;
+            size_t nFindFailed = 0;
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                work_thread& thr = static_cast<work_thread&>( pool.get( i ));
+                nInsertSuccess += thr.m_nInsertSuccess;
+                nInsertFailed  += thr.m_nInsertFailed;
+                nDeleteSuccess += thr.m_nDeleteSuccess;
+                nDeleteFailed  += thr.m_nDeleteFailed;
+                nFindSuccess   += thr.m_nFindSuccess;
+                nFindFailed    += thr.m_nFindFailed;
+            }
+
+            propout()
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "find_success", nFindSuccess )
+                << std::make_pair( "find_failed", nFindFailed );
+
+            {
+                ASSERT_TRUE( std::chrono::duration_cast<std::chrono::seconds>(duration).count() > 0 );
+                size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
+                propout() << std::make_pair( "avg_speed", nTotalOps / std::chrono::duration_cast<std::chrono::seconds>(duration).count());
+            }
+
+
+            testSet.clear();
+            EXPECT_TRUE( testSet.empty()) << "set size=" << testSet.size();
+
+            additional_check( testSet );
+            print_stat( propout(), testSet );
+            additional_cleanup( testSet );
+        }
+
+        template <class Set>
+        void run_test()
+        {
+            Set s( *this );
+            do_test( s );
+        }
+    };
+
+    class Set_InsDelFind_LF: public Set_InsDelFind
+        , public ::testing::WithParamInterface<size_t>
+    {
+    public:
+        template <class Set>
+        void run_test()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_InsDelFind::run_test<Set>();
+        }
+
+        static std::vector<size_t> get_load_factors();
+    };
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_cuckoo.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_cuckoo.cpp
new file mode 100644 (file)
index 0000000..fc00355
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_cuckoo.h"
+
+namespace set {
+
+    //CDSSTRESS_CuckooSet( Set_InsDelFind, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_ellentree_hp.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_ellentree_hp.cpp
new file mode 100644 (file)
index 0000000..adfd592
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_ellen_bintree.h"
+
+namespace set {
+
+    CDSSTRESS_EllenBinTreeSet_HP( Set_InsDelFind, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_ellentree_rcu.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_ellentree_rcu.cpp
new file mode 100644 (file)
index 0000000..11906ea
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_ellen_bintree.h"
+
+namespace set {
+
+    CDSSTRESS_EllenBinTreeSet_RCU( Set_InsDelFind, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_feldman_hashset_hp.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_feldman_hashset_hp.cpp
new file mode 100644 (file)
index 0000000..7e6a68e
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_feldman_hashset.h"
+
+namespace set {
+
+    CDSSTRESS_FeldmanHashSet_fixed_HP( Set_InsDelFind, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_feldman_hashset_rcu.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_feldman_hashset_rcu.cpp
new file mode 100644 (file)
index 0000000..423cfdd
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_feldman_hashset.h"
+
+namespace set {
+
+    CDSSTRESS_FeldmanHashSet_fixed_RCU( Set_InsDelFind, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_michael_hp.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_michael_hp.cpp
new file mode 100644 (file)
index 0000000..d43ae5d
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_michael.h"
+
+namespace set {
+
+    CDSSTRESS_MichaelSet_HP( Set_InsDelFind_LF, run_test, size_t, size_t )
+    CDSSTRESS_MichaelIterableSet( Set_InsDelFind_LF, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_michael_rcu.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_michael_rcu.cpp
new file mode 100644 (file)
index 0000000..0006b83
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_michael.h"
+
+namespace set {
+
+    CDSSTRESS_MichaelSet_RCU( Set_InsDelFind_LF, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_skip_hp.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_skip_hp.cpp
new file mode 100644 (file)
index 0000000..539d0d9
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_skip_list.h"
+
+namespace set {
+
+    CDSSTRESS_SkipListSet_HP( Set_InsDelFind, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_skip_rcu.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_skip_rcu.cpp
new file mode 100644 (file)
index 0000000..9ecaceb
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_skip_list.h"
+
+namespace set {
+
+    CDSSTRESS_SkipListSet_RCU( Set_InsDelFind, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_split_hp.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_split_hp.cpp
new file mode 100644 (file)
index 0000000..35a3ca6
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_split_list.h"
+
+namespace set {
+
+    CDSSTRESS_SplitListSet_HP( Set_InsDelFind_LF, run_test, size_t, size_t )
+    CDSSTRESS_SplitListIterableSet( Set_InsDelFind_LF, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_split_rcu.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_split_rcu.cpp
new file mode 100644 (file)
index 0000000..d0f98b7
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_split_list.h"
+
+namespace set {
+
+    CDSSTRESS_SplitListSet_RCU( Set_InsDelFind_LF, run_test, size_t, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_std.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_std.cpp
new file mode 100644 (file)
index 0000000..75d6fa5
--- /dev/null
@@ -0,0 +1,37 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_std.h"
+
+namespace set {
+    //CDSSTRESS_StdSet( Set_InsDelFind, run_test, size_t, size_t )
+} // namespace set
+
diff --git a/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_striped.cpp b/test/stress/sequential/sequential-set/insdel_find/set_insdelfind_striped.cpp
new file mode 100644 (file)
index 0000000..7f89f64
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdelfind.h"
+#include "set_type_striped.h"
+
+namespace set {
+
+    //CDSSTRESS_StripedSet( Set_InsDelFind_LF, run_test, size_t, size_t )
+
+} // namespace set
+
diff --git a/test/stress/sequential/sequential-set/insdel_func/CMakeLists.txt b/test/stress/sequential/sequential-set/insdel_func/CMakeLists.txt
new file mode 100644 (file)
index 0000000..555b7a1
--- /dev/null
@@ -0,0 +1,23 @@
+set(PACKAGE_NAME stress-sequential-set-insdel-func)
+
+set(CDSSTRESS_SET_INSDEL_FUNC_SOURCES
+    ../../../main.cpp
+    set_insdel_func.cpp
+    set_insdel_func_cuckoo.cpp
+    set_insdel_func_ellentree.cpp
+    set_insdel_func_feldman_hashset.cpp
+    set_insdel_func_michael.cpp
+    set_insdel_func_skip.cpp
+    set_insdel_func_split.cpp
+    set_insdel_func_striped.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_SET_INSDEL_FUNC_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func.cpp
new file mode 100644 (file)
index 0000000..9ce8d9a
--- /dev/null
@@ -0,0 +1,122 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+
+namespace set {
+
+    size_t Set_InsDel_func::s_nSetSize = 1000000;      // set size
+    size_t Set_InsDel_func::s_nInsertThreadCount = 4;  // count of insertion thread
+    size_t Set_InsDel_func::s_nDeleteThreadCount = 4;  // count of deletion thread
+    size_t Set_InsDel_func::s_nUpdateThreadCount = 4;  // count of ensure thread
+    size_t Set_InsDel_func::s_nThreadPassCount = 4;    // pass count for each thread
+    size_t Set_InsDel_func::s_nMaxLoadFactor = 8;      // maximum load factor
+
+    size_t Set_InsDel_func::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+    size_t Set_InsDel_func::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+    size_t Set_InsDel_func::s_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+    size_t Set_InsDel_func::s_nFeldmanSet_HeadBits = 10;
+    size_t Set_InsDel_func::s_nFeldmanSet_ArrayBits = 4;
+
+    size_t Set_InsDel_func::s_nLoadFactor = 1;
+
+    void Set_InsDel_func::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "map_insdel_func" );
+
+        s_nSetSize = cfg.get_size_t( "MapSize", s_nSetSize );
+        if ( s_nSetSize < 1000 )
+            s_nSetSize = 1000;
+
+        s_nInsertThreadCount = cfg.get_size_t( "InsertThreadCount", s_nInsertThreadCount );
+        if ( s_nInsertThreadCount == 0 )
+            s_nInsertThreadCount = 2;
+
+        s_nDeleteThreadCount = cfg.get_size_t( "DeleteThreadCount", s_nDeleteThreadCount );
+        if ( s_nDeleteThreadCount == 0 )
+            s_nDeleteThreadCount = 2;
+
+        s_nUpdateThreadCount = cfg.get_size_t( "UpdateThreadCount", s_nUpdateThreadCount );
+        if ( s_nUpdateThreadCount == 0 )
+            s_nUpdateThreadCount = 2;
+
+        s_nThreadPassCount = cfg.get_size_t( "ThreadPassCount", s_nThreadPassCount );
+        if ( s_nThreadPassCount == 0 )
+            s_nThreadPassCount = 4;
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+        if ( s_nCuckooInitialSize < 256 )
+            s_nCuckooInitialSize = 256;
+
+        s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+        if ( s_nCuckooProbesetSize < 8 )
+            s_nCuckooProbesetSize = 8;
+
+        s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+        s_nFeldmanSet_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanSet_HeadBits );
+        if ( s_nFeldmanSet_HeadBits == 0 )
+            s_nFeldmanSet_HeadBits = 2;
+
+        s_nFeldmanSet_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanSet_ArrayBits );
+        if ( s_nFeldmanSet_ArrayBits == 0 )
+            s_nFeldmanSet_ArrayBits = 2;
+    }
+
+    std::vector<size_t> Set_InsDel_func_LF::get_load_factors()
+    {
+        cds_test::config const& cfg = get_config( "map_insdel_func" );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        std::vector<size_t> lf;
+        for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+            lf.push_back( n );
+
+        return lf;
+    }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+    static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+    {
+        return std::to_string( p.param );
+    }
+    INSTANTIATE_TEST_CASE_P( a, Set_InsDel_func_LF, ::testing::ValuesIn( Set_InsDel_func_LF::get_load_factors()), get_test_parameter_name );
+#else
+    INSTANTIATE_TEST_CASE_P( a, Set_InsDel_func_LF, ::testing::ValuesIn( Set_InsDel_func_LF::get_load_factors()));
+#endif
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func.h b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func.h
new file mode 100644 (file)
index 0000000..d7b4439
--- /dev/null
@@ -0,0 +1,564 @@
+/*
+    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.
+*/
+
+#include "set_type.h"
+
+namespace set {
+
+    class Set_InsDel_func: public cds_test::stress_fixture
+    {
+    public:
+        static size_t s_nSetSize;               // set size
+        static size_t s_nInsertThreadCount;     // count of insertion thread
+        static size_t s_nDeleteThreadCount;     // count of deletion thread
+        static size_t s_nUpdateThreadCount;     // count of updating thread
+        static size_t s_nThreadPassCount;       // pass count for each thread
+        static size_t s_nMaxLoadFactor;         // maximum load factor
+
+        static size_t s_nCuckooInitialSize;     // initial size for CuckooSet
+        static size_t s_nCuckooProbesetSize;    // CuckooSet probeset size (only for list-based probeset)
+        static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
+
+        static size_t s_nFeldmanSet_HeadBits;
+        static size_t s_nFeldmanSet_ArrayBits;
+
+        static size_t s_nLoadFactor;
+
+        static void SetUpTestCase();
+        //static void TearDownTestCase();
+
+    public:
+        typedef size_t  key_type;
+
+        struct value {
+            size_t      nKey;
+            size_t      nData;
+            atomics::atomic<size_t> nUpdateCall;
+            bool volatile           bInitialized;
+            cds::OS::ThreadId       threadId;   // insert thread id
+
+            typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
+            mutable lock_type   m_access;
+
+            value()
+                : nKey(0)
+                , nData(0)
+                , nUpdateCall(0)
+                , bInitialized( false )
+                , threadId( cds::OS::get_current_thread_id())
+            {}
+
+            value( value const& s )
+                : nKey(s.nKey)
+                , nData(s.nData)
+                , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed))
+                , bInitialized( s.bInitialized )
+                , threadId( cds::OS::get_current_thread_id())
+                , m_access()
+            {}
+
+            // boost::container::flat_map requires operator =
+            // cppcheck-suppress operatorEqVarError
+            value& operator=( value const& v )
+            {
+                nKey = v.nKey;
+                nData = v.nData;
+                threadId = v.threadId;
+                nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
+                bInitialized = v.bInitialized;
+
+                return *this;
+            }
+        };
+
+        size_t *    m_pKeyFirst;
+        size_t *    m_pKeyLast;
+        std::unique_ptr< size_t[] > m_pKeyArr;
+
+        enum {
+            insert_thread,
+            update_thread,
+            delete_thread
+        };
+
+        template <class Set>
+        class Inserter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+
+            Set&     m_Set;
+            typedef typename Set::value_type keyval_type;
+
+            struct insert_functor {
+                size_t nTestFunctorRef;
+
+                insert_functor()
+                    : nTestFunctorRef(0)
+                {}
+                insert_functor( insert_functor const& ) = delete;
+
+                void operator()( keyval_type& val )
+                {
+                    std::unique_lock< typename value::lock_type> ac( val.val.m_access );
+
+                    val.val.nKey  = val.key;
+                    val.val.nData = val.key * 8;
+
+                    ++nTestFunctorRef;
+                    val.val.bInitialized = true;
+                }
+            };
+
+        public:
+            size_t  m_nInsertSuccess = 0;
+            size_t  m_nInsertFailed = 0;
+            size_t  m_nTestFunctorRef = 0;
+
+        public:
+            Inserter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, insert_thread )
+                , m_Set( set )
+            {}
+
+            Inserter( Inserter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Inserter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
+
+                size_t * pKeyFirst      = fixture.m_pKeyFirst;
+                size_t * pKeyLast       = fixture.m_pKeyLast;
+                size_t const nPassCount = fixture.s_nThreadPassCount;
+
+                // func is passed by reference
+                insert_functor  func;
+
+                if ( id() & 1 ) {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
+                            if ( rSet.insert( *p, std::ref( func )))
+                                ++m_nInsertSuccess;
+                            else
+                                ++m_nInsertFailed;
+                        }
+                    }
+                }
+                else {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
+                            if ( rSet.insert( *p, std::ref( func )))
+                                ++m_nInsertSuccess;
+                            else
+                                ++m_nInsertFailed;
+                        }
+                    }
+                }
+
+                m_nTestFunctorRef = func.nTestFunctorRef;
+            }
+        };
+
+        template <class Set>
+        class Updater: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+
+            Set&     m_Set;
+            typedef typename Set::value_type keyval_type;
+
+            struct update_functor {
+                size_t  nCreated = 0;
+                size_t  nModified = 0;
+
+                update_functor() {}
+                update_functor( const update_functor& ) = delete;
+
+                void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
+                {
+                    std::unique_lock<typename value::lock_type> ac( val.val.m_access );
+                    if ( !val.val.bInitialized )
+                    {
+                        val.val.nKey = val.key;
+                        val.val.nData = val.key * 8;
+                        val.val.bInitialized = true;
+                    }
+
+                    if ( bNew ) {
+                        ++nCreated;
+                    }
+                    else {
+                        val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
+                        ++nModified;
+                    }
+                }
+
+                void operator()( keyval_type& cur, keyval_type * old )
+                {
+                    operator()( old == nullptr, cur, 0 );
+                }
+            };
+
+        public:
+            size_t  m_nUpdateFailed = 0;
+            size_t  m_nUpdateCreated = 0;
+            size_t  m_nUpdateExisted = 0;
+            size_t  m_nFunctorCreated = 0;
+            size_t  m_nFunctorModified = 0;
+
+        public:
+            Updater( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, update_thread )
+                , m_Set( set )
+            {}
+
+            Updater( Updater& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Updater( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
+                size_t * pKeyFirst = fixture.m_pKeyFirst;
+                size_t * pKeyLast = fixture.m_pKeyLast;
+                size_t const nPassCount = fixture.s_nThreadPassCount;
+
+                update_functor func;
+
+                if ( id() & 1 ) {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
+                            std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
+                            if ( ret.first  ) {
+                                if ( ret.second )
+                                    ++m_nUpdateCreated;
+                                else
+                                    ++m_nUpdateExisted;
+                            }
+                            else
+                                ++m_nUpdateFailed;
+                        }
+                    }
+                }
+                else {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
+                            std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
+                            if ( ret.first  ) {
+                                if ( ret.second )
+                                    ++m_nUpdateCreated;
+                                else
+                                    ++m_nUpdateExisted;
+                            }
+                            else
+                                ++m_nUpdateFailed;
+                        }
+                    }
+                }
+
+                m_nFunctorCreated = func.nCreated;
+                m_nFunctorModified = func.nModified;
+            }
+        };
+
+        template <class Set>
+        class Deleter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+
+            Set&     m_Set;
+            typedef typename Set::value_type keyval_type;
+
+            struct value_container
+            {
+                size_t      nKeyExpected;
+
+                size_t      nSuccessItem = 0;
+                size_t      nFailedItem = 0;
+            };
+
+            struct erase_functor {
+                value_container     m_cnt;
+
+                void operator ()( keyval_type const& itm )
+                {
+                    keyval_type& item = const_cast<keyval_type&>(itm);
+                    while ( true ) {
+                        bool bBkoff = false;
+                        {
+                            std::unique_lock< typename value::lock_type> ac( item.val.m_access );
+                            if ( item.val.bInitialized ) {
+                                if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
+                                    ++m_cnt.nSuccessItem;
+                                else
+                                    ++m_cnt.nFailedItem;
+                                item.val.nData++;
+                                item.val.nKey = 0;
+                                break;
+                            }
+                            else
+                                bBkoff = true;
+                        }
+                        if ( bBkoff )
+                            cds::backoff::yield()();
+                    }
+                }
+            };
+
+        public:
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+            size_t  m_nValueSuccess = 0;
+            size_t  m_nValueFailed = 0;
+
+        public:
+            Deleter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, delete_thread )
+                , m_Set( set )
+            {}
+
+            Deleter( Deleter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Deleter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
+                size_t * pKeyFirst      = fixture.m_pKeyFirst;
+                size_t * pKeyLast       = fixture.m_pKeyLast;
+                size_t const nPassCount = fixture.s_nThreadPassCount;
+
+                erase_functor   func;
+
+                if ( id() & 1 ) {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
+                            func.m_cnt.nKeyExpected = *p;
+                            if ( rSet.erase( *p, std::ref( func )))
+                                ++m_nDeleteSuccess;
+                            else
+                                ++m_nDeleteFailed;
+                        }
+                    }
+                }
+                else {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
+                            func.m_cnt.nKeyExpected = *p;
+                            if ( rSet.erase( *p, std::ref( func )))
+                                ++m_nDeleteSuccess;
+                            else
+                                ++m_nDeleteFailed;
+                        }
+                    }
+                }
+
+                m_nValueSuccess = func.m_cnt.nSuccessItem;
+                m_nValueFailed = func.m_cnt.nFailedItem;
+            }
+        };
+
+    protected:
+
+        template <class Set>
+        void run_test( Set& testSet )
+        {
+            typedef Inserter<Set>       InserterThread;
+            typedef Deleter<Set>        DeleterThread;
+            typedef Updater<Set>        UpdaterThread;
+
+            m_pKeyArr.reset( new size_t[ s_nSetSize ] );
+            m_pKeyFirst = m_pKeyArr.get();
+            m_pKeyLast = m_pKeyFirst + s_nSetSize;
+            for ( size_t i = 0; i < s_nSetSize; ++i )
+                m_pKeyArr[i] = i;
+            shuffle( m_pKeyFirst, m_pKeyLast );
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
+            pool.add( new DeleterThread( pool, testSet ),  s_nDeleteThreadCount );
+            pool.add( new UpdaterThread( pool, testSet ),  s_nUpdateThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
+                << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
+                << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
+                << std::make_pair( "thread_pass_count", s_nThreadPassCount )
+                << std::make_pair( "set_size", s_nSetSize );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+            size_t nDelValueSuccess = 0;
+            size_t nDelValueFailed = 0;
+            size_t nUpdateFailed = 0;
+            size_t nUpdateCreated = 0;
+            size_t nUpdateModified = 0;
+            size_t nEnsFuncCreated = 0;
+            size_t nEnsFuncModified = 0;
+            size_t nTestFunctorRef = 0;
+
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case insert_thread:
+                    {
+                        InserterThread& inserter = static_cast<InserterThread&>( thr );
+                        nInsertSuccess  += inserter.m_nInsertSuccess;
+                        nInsertFailed   += inserter.m_nInsertFailed;
+                        nTestFunctorRef += inserter.m_nTestFunctorRef;
+                    }
+                    break;
+                case update_thread:
+                    {
+                        UpdaterThread& updater = static_cast<UpdaterThread&>(thr);
+                        nUpdateCreated   += updater.m_nUpdateCreated;
+                        nUpdateModified  += updater.m_nUpdateExisted;
+                        nUpdateFailed    += updater.m_nUpdateFailed;
+                        nEnsFuncCreated  += updater.m_nFunctorCreated;
+                        nEnsFuncModified += updater.m_nFunctorModified;
+                    }
+                    break;
+                case delete_thread:
+                    {
+                        DeleterThread& deleter = static_cast<DeleterThread&>(thr);
+                        nDeleteSuccess   += deleter.m_nDeleteSuccess;
+                        nDeleteFailed    += deleter.m_nDeleteFailed;
+                        nDelValueSuccess += deleter.m_nValueSuccess;
+                        nDelValueFailed  += deleter.m_nValueFailed;
+                    }
+                    break;
+                }
+            }
+
+            propout()
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "update_created", nUpdateCreated )
+                << std::make_pair( "update_modified", nUpdateModified )
+                << std::make_pair( "update_failed", nUpdateFailed )
+                << std::make_pair( "final_set_size", testSet.size());
+
+
+            EXPECT_EQ( nDelValueFailed, 0u );
+            EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
+
+            EXPECT_EQ( nUpdateFailed, 0u );
+            EXPECT_EQ( nUpdateCreated, nEnsFuncCreated );
+            EXPECT_EQ( nUpdateModified, nEnsFuncModified );
+
+            // nTestFunctorRef is call count of insert functor
+            EXPECT_EQ( nTestFunctorRef, nInsertSuccess );
+
+            //testSet.clear();
+            for ( size_t * p = m_pKeyFirst; p != m_pKeyLast; ++p )
+                testSet.erase( *p );
+
+            EXPECT_TRUE( testSet.empty());
+            EXPECT_EQ( testSet.size(), 0u );
+
+            additional_check( testSet );
+            print_stat( propout(), testSet  );
+
+            additional_cleanup( testSet );
+        }
+
+        template <class Set>
+        void run_test()
+        {
+            Set s( *this );
+            run_test( s );
+        }
+
+        template <class Set>
+        void run_test2()
+        {
+            Set s( *this );
+            run_test( s );
+
+            for ( auto it = s.begin(); it != s.end(); ++it )
+                std::cout << "key=" << it->key << std::endl;
+        }
+    };
+
+    class Set_InsDel_func_LF: public Set_InsDel_func
+        , public ::testing::WithParamInterface<size_t>
+    {
+    public:
+        template <class Set>
+        void run_test()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_InsDel_func::run_test<Set>();
+        }
+
+        template <class Set>
+        void run_test2()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_InsDel_func::run_test2<Set>();
+        }
+
+        static std::vector<size_t> get_load_factors();
+    };
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_cuckoo.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_cuckoo.cpp
new file mode 100644 (file)
index 0000000..865ae34
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+#include "set_type_cuckoo.h"
+
+namespace set {
+
+    //CDSSTRESS_CuckooSet( Set_InsDel_func, run_test, size_t, value )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_ellentree.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_ellentree.cpp
new file mode 100644 (file)
index 0000000..42235d5
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+#include "set_type_ellen_bintree.h"
+
+namespace set {
+
+    CDSSTRESS_EllenBinTreeSet( Set_InsDel_func, run_test, size_t, value )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_feldman_hashset.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_feldman_hashset.cpp
new file mode 100644 (file)
index 0000000..b918eb2
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+#include "set_type_feldman_hashset.h"
+
+namespace set {
+
+    CDSSTRESS_FeldmanHashSet_fixed( Set_InsDel_func, run_test, size_t, value )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_michael.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_michael.cpp
new file mode 100644 (file)
index 0000000..bef6282
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+#include "set_type_michael.h"
+
+namespace set {
+
+    CDSSTRESS_MichaelSet( Set_InsDel_func_LF, run_test2, size_t, value )
+    CDSSTRESS_MichaelIterableSet( Set_InsDel_func_LF, run_test2, size_t, value )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_skip.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_skip.cpp
new file mode 100644 (file)
index 0000000..1027219
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+#include "set_type_skip_list.h"
+
+namespace set {
+
+    CDSSTRESS_SkipListSet( Set_InsDel_func, run_test, size_t, value )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_split.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_split.cpp
new file mode 100644 (file)
index 0000000..a752c4d
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+#include "set_type_split_list.h"
+
+namespace set {
+
+    CDSSTRESS_SplitListSet( Set_InsDel_func_LF, run_test, size_t, value )
+    CDSSTRESS_SplitListIterableSet( Set_InsDel_func_LF, run_test, size_t, value )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_striped.cpp b/test/stress/sequential/sequential-set/insdel_func/set_insdel_func_striped.cpp
new file mode 100644 (file)
index 0000000..9fdbdf6
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdel_func.h"
+#include "set_type_striped.h"
+
+namespace set {
+
+    //CDSSTRESS_StripedSet( Set_InsDel_func_LF, run_test, size_t, value )
+
+} // namespace set
+
diff --git a/test/stress/sequential/sequential-set/insdel_string/CMakeLists.txt b/test/stress/sequential/sequential-set/insdel_string/CMakeLists.txt
new file mode 100644 (file)
index 0000000..4b780b4
--- /dev/null
@@ -0,0 +1,24 @@
+set(PACKAGE_NAME stress-sequential-set-insdel-string)
+
+set(CDSSTRESS_SET_INSDEL_STRING_SOURCES
+    ../../../main.cpp
+    set_insdel_string.cpp
+    set_insdel_string_cuckoo.cpp
+    set_insdel_string_ellentree.cpp
+    set_insdel_string_feldman_hashset.cpp
+    set_insdel_string_michael.cpp
+    set_insdel_string_skip.cpp
+    set_insdel_string_split.cpp
+    set_insdel_string_std.cpp
+    set_insdel_string_striped.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_SET_INSDEL_STRING_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string.cpp
new file mode 100644 (file)
index 0000000..40f066e
--- /dev/null
@@ -0,0 +1,128 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+
+namespace set {
+
+    size_t Set_InsDel_string::s_nSetSize = 1000000;      // set size
+    size_t Set_InsDel_string::s_nInsertThreadCount = 4;  // count of insertion thread
+    size_t Set_InsDel_string::s_nDeleteThreadCount = 4;  // count of deletion thread
+    size_t Set_InsDel_string::s_nThreadPassCount = 4;    // pass count for each thread
+    size_t Set_InsDel_string::s_nMaxLoadFactor = 8;      // maximum load factor
+
+    size_t Set_InsDel_string::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+    size_t Set_InsDel_string::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+    size_t Set_InsDel_string::s_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+    size_t Set_InsDel_string::s_nFeldmanSet_HeadBits = 10;
+    size_t Set_InsDel_string::s_nFeldmanSet_ArrayBits = 4;
+
+    size_t Set_InsDel_string::s_nLoadFactor = 1;
+    std::vector<std::string> Set_InsDel_string::m_arrString;
+
+    void Set_InsDel_string::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "map_insdel_string" );
+
+        s_nSetSize = cfg.get_size_t( "MapSize", s_nSetSize );
+        if ( s_nSetSize < 1000 )
+            s_nSetSize = 1000;
+
+        s_nInsertThreadCount = cfg.get_size_t( "InsertThreadCount", s_nInsertThreadCount );
+        if ( s_nInsertThreadCount == 0 )
+            s_nInsertThreadCount = 2;
+
+        s_nDeleteThreadCount = cfg.get_size_t( "DeleteThreadCount", s_nDeleteThreadCount );
+        if ( s_nDeleteThreadCount == 0 )
+            s_nDeleteThreadCount = 2;
+
+        s_nThreadPassCount = cfg.get_size_t( "ThreadPassCount", s_nThreadPassCount );
+        if ( s_nThreadPassCount == 0 )
+            s_nThreadPassCount = 4;
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+        if ( s_nCuckooInitialSize < 256 )
+            s_nCuckooInitialSize = 256;
+
+        s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+        if ( s_nCuckooProbesetSize < 8 )
+            s_nCuckooProbesetSize = 8;
+
+        s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+        s_nFeldmanSet_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanSet_HeadBits );
+        if ( s_nFeldmanSet_HeadBits == 0 )
+            s_nFeldmanSet_HeadBits = 2;
+
+        s_nFeldmanSet_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanSet_ArrayBits );
+        if ( s_nFeldmanSet_ArrayBits == 0 )
+            s_nFeldmanSet_ArrayBits = 2;
+
+        // Load string dictionary
+        m_arrString = load_dictionary();
+    }
+
+    void Set_InsDel_string::TearDownTestCase()
+    {
+        m_arrString.clear();
+    }
+
+    std::vector<size_t> Set_InsDel_string_LF::get_load_factors()
+    {
+        cds_test::config const& cfg = get_config( "map_insdel_string" );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        std::vector<size_t> lf;
+        for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+            lf.push_back( n );
+
+        return lf;
+    }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+    static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+    {
+        return std::to_string( p.param );
+    }
+    INSTANTIATE_TEST_CASE_P( a, Set_InsDel_string_LF, ::testing::ValuesIn( Set_InsDel_string_LF::get_load_factors()), get_test_parameter_name );
+#else
+    INSTANTIATE_TEST_CASE_P( a, Set_InsDel_string_LF, ::testing::ValuesIn( Set_InsDel_string_LF::get_load_factors()));
+#endif
+
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string.h b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string.h
new file mode 100644 (file)
index 0000000..ad1a1b6
--- /dev/null
@@ -0,0 +1,521 @@
+/*
+    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.
+*/
+
+#include "set_type.h"
+
+namespace set {
+
+#define TEST_CASE(TAG, X)  void X();
+
+    class Set_InsDel_string: public cds_test::stress_fixture
+    {
+    public:
+        static size_t s_nSetSize;               // set size
+        static size_t s_nInsertThreadCount;     // count of insertion thread
+        static size_t s_nDeleteThreadCount;     // count of deletion thread
+        static size_t s_nThreadPassCount;       // pass count for each thread
+        static size_t s_nMaxLoadFactor;         // maximum load factor
+
+        static size_t s_nCuckooInitialSize;     // initial size for CuckooSet
+        static size_t s_nCuckooProbesetSize;    // CuckooSet probeset size (only for list-based probeset)
+        static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
+
+        static size_t s_nFeldmanSet_HeadBits;
+        static size_t s_nFeldmanSet_ArrayBits;
+
+        static size_t s_nLoadFactor;
+        static std::vector<std::string>  m_arrString;
+
+        static void SetUpTestCase();
+        static void TearDownTestCase();
+
+    private:
+        typedef std::string key_type;
+        typedef size_t      value_type;
+
+        enum {
+            insert_thread,
+            delete_thread,
+            extract_thread
+        };
+
+        template <class Set>
+        class Inserter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+
+            Set&     m_Set;
+            typedef typename Set::value_type    keyval_type;
+
+        public:
+            size_t  m_nInsertSuccess = 0;
+            size_t  m_nInsertFailed = 0;
+
+        public:
+            Inserter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, insert_thread )
+                , m_Set( set )
+            {}
+
+            Inserter( Inserter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Inserter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
+                size_t nArrSize = m_arrString.size();
+                size_t const nSetSize = fixture.s_nSetSize;
+                size_t const nPassCount = fixture.s_nThreadPassCount;
+
+                if ( id() & 1 ) {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
+                            if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
+                                ++m_nInsertSuccess;
+                            else
+                                ++m_nInsertFailed;
+                        }
+                    }
+                }
+                else {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
+                            if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
+                                ++m_nInsertSuccess;
+                            else
+                                ++m_nInsertFailed;
+                        }
+                    }
+                }
+            }
+        };
+
+        template <class Set>
+        class Deleter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+
+            Set&     m_Set;
+        public:
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+
+        public:
+            Deleter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, delete_thread )
+                , m_Set( set )
+            {}
+
+            Deleter( Deleter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Deleter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
+                size_t nArrSize = m_arrString.size();
+                size_t const nSetSize = fixture.s_nSetSize;
+                size_t const nPassCount = fixture.s_nThreadPassCount;
+
+                if ( id() & 1 ) {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
+                            if ( rSet.erase( m_arrString[nItem % nArrSize] ))
+                                ++m_nDeleteSuccess;
+                            else
+                                ++m_nDeleteFailed;
+                        }
+                    }
+                }
+                else {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
+                            if ( rSet.erase( m_arrString[nItem % nArrSize] ))
+                                ++m_nDeleteSuccess;
+                            else
+                                ++m_nDeleteFailed;
+                        }
+                    }
+                }
+            }
+        };
+
+        template <typename GC, class Set>
+        class Extractor: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+        public:
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extract_thread )
+                , m_Set( set )
+            {}
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                typename Set::guarded_ptr gp;
+
+                Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
+                size_t nArrSize = m_arrString.size();
+                size_t const nSetSize = fixture.s_nSetSize;
+                size_t const nPassCount = fixture.s_nThreadPassCount;
+
+                if ( id() & 1 ) {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
+                            gp = rSet.extract( m_arrString[nItem % nArrSize] );
+                            if ( gp )
+                                ++m_nDeleteSuccess;
+                            else
+                                ++m_nDeleteFailed;
+                            gp.release();
+                        }
+                    }
+                }
+                else {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
+                            gp = rSet.extract( m_arrString[nItem % nArrSize] );
+                            if ( gp )
+                                ++m_nDeleteSuccess;
+                            else
+                                ++m_nDeleteFailed;
+                            gp.release();
+                        }
+                    }
+                }
+            }
+        };
+
+        template <typename RCU, class Set>
+        class Extractor<cds::urcu::gc<RCU>, Set >: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+        public:
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extract_thread )
+                , m_Set( set )
+            {}
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                typename Set::exempt_ptr xp;
+
+                Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
+                size_t nArrSize = m_arrString.size();
+                size_t const nSetSize = fixture.s_nSetSize;
+                size_t const nPassCount = fixture.s_nThreadPassCount;
+
+                if ( id() & 1 ) {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
+                            if ( Set::c_bExtractLockExternal ) {
+                                typename Set::rcu_lock l;
+                                xp = rSet.extract( m_arrString[nItem % nArrSize] );
+                                if ( xp )
+                                    ++m_nDeleteSuccess;
+                                else
+                                    ++m_nDeleteFailed;
+                            }
+                            else {
+                                xp = rSet.extract( m_arrString[nItem % nArrSize] );
+                                if ( xp )
+                                    ++m_nDeleteSuccess;
+                                else
+                                    ++m_nDeleteFailed;
+                            }
+                            xp.release();
+                        }
+                    }
+                }
+                else {
+                    for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
+                        for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
+                            if ( Set::c_bExtractLockExternal ) {
+                                typename Set::rcu_lock l;
+                                xp = rSet.extract( m_arrString[nItem % nArrSize] );
+                                if ( xp )
+                                    ++m_nDeleteSuccess;
+                                else
+                                    ++m_nDeleteFailed;
+                            }
+                            else {
+                                xp = rSet.extract( m_arrString[nItem % nArrSize] );
+                                if ( xp )
+                                    ++m_nDeleteSuccess;
+                                else
+                                    ++m_nDeleteFailed;
+                            }
+                            xp.release();
+                        }
+                    }
+                }
+            }
+        };
+
+    protected:
+        template <class Set>
+        void do_test( Set& testSet )
+        {
+            typedef Inserter<Set> InserterThread;
+            typedef Deleter<Set>  DeleterThread;
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
+            pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
+                << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
+                << std::make_pair( "thread_pass_count", s_nThreadPassCount )
+                << std::make_pair( "set_size", s_nSetSize );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case insert_thread:
+                    {
+                        InserterThread& inserter = static_cast<InserterThread&>( thr );
+                        nInsertSuccess += inserter.m_nInsertSuccess;
+                        nInsertFailed += inserter.m_nInsertFailed;
+                    }
+                    break;
+                case delete_thread:
+                    {
+                        DeleterThread& deleter = static_cast<DeleterThread&>(thr);
+                        nDeleteSuccess += deleter.m_nDeleteSuccess;
+                        nDeleteFailed += deleter.m_nDeleteFailed;
+                }
+                    break;
+                default:
+                    assert( false ); // Forgot anything?..
+                }
+            }
+
+            propout()
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "final_set_size", testSet.size());
+
+            //testSet.clear();
+            for (auto const& str: m_arrString )
+                testSet.erase( str );
+            EXPECT_TRUE( testSet.empty());
+            EXPECT_EQ( testSet.size(), 0u );
+
+            additional_check( testSet );
+            print_stat( propout(), testSet );
+            additional_cleanup( testSet );
+        }
+
+        template <class Set>
+        void do_test_extract( Set& testSet )
+        {
+            typedef Inserter<Set> InserterThread;
+            typedef Deleter<Set>  DeleterThread;
+            typedef Extractor<typename Set::gc, Set> ExtractThread;
+
+            size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
+            size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
+            pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
+            pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
+                << std::make_pair( "delete_thread_count", nDelThreadCount )
+                << std::make_pair( "extract_thread_count", nExtractThreadCount )
+                << std::make_pair( "thread_pass_count", s_nThreadPassCount )
+                << std::make_pair( "set_size", s_nSetSize );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+            size_t nExtractSuccess = 0;
+            size_t nExtractFailed = 0;
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case insert_thread:
+                    {
+                        InserterThread& inserter = static_cast<InserterThread&>(thr);
+                        nInsertSuccess += inserter.m_nInsertSuccess;
+                        nInsertFailed += inserter.m_nInsertFailed;
+                    }
+                    break;
+                case delete_thread:
+                    {
+                        DeleterThread& deleter = static_cast<DeleterThread&>(thr);
+                        nDeleteSuccess += deleter.m_nDeleteSuccess;
+                        nDeleteFailed += deleter.m_nDeleteFailed;
+                    }
+                    break;
+                case extract_thread:
+                    {
+                        ExtractThread& extractor = static_cast<ExtractThread&>(thr);
+                        nExtractSuccess += extractor.m_nDeleteSuccess;
+                        nExtractFailed += extractor.m_nDeleteFailed;
+                    }
+                    break;
+                default:
+                    assert( false ); // Forgot anything?..
+                }
+            }
+
+            propout()
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "extract_success", nExtractSuccess )
+                << std::make_pair( "insert_failed",  nInsertFailed )
+                << std::make_pair( "delete_failed",  nDeleteFailed )
+                << std::make_pair( "extract_failed", nExtractFailed )
+                << std::make_pair( "final_set_size", testSet.size());
+
+            //testSet.clear();
+            for ( auto const& str : m_arrString )
+                testSet.erase( str );
+            EXPECT_TRUE( testSet.empty());
+            EXPECT_EQ( testSet.size(), 0u );
+
+            additional_check( testSet );
+            print_stat( propout(), testSet );
+            additional_cleanup( testSet );
+        }
+
+        template <class Set>
+        void run_test()
+        {
+            ASSERT_TRUE( m_arrString.size() > 0 );
+
+            Set s( *this );
+            do_test( s );
+        }
+
+        template <class Set>
+        void run_test_extract()
+        {
+            ASSERT_TRUE( m_arrString.size() > 0 );
+
+            Set s( *this );
+            do_test_extract( s );
+        }
+    };
+
+    class Set_InsDel_string_LF: public Set_InsDel_string
+        , public ::testing::WithParamInterface<size_t>
+    {
+    public:
+        template <class Set>
+        void run_test()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_InsDel_string::run_test<Set>();
+        }
+
+        template <class Set>
+        void run_test_extract()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_InsDel_string::run_test_extract<Set>();
+        }
+
+        static std::vector<size_t> get_load_factors();
+    };
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_cuckoo.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_cuckoo.cpp
new file mode 100644 (file)
index 0000000..83892c3
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_cuckoo.h"
+
+namespace set {
+
+    //CDSSTRESS_CuckooSet( Set_InsDel_string, run_test, std::string, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_ellentree.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_ellentree.cpp
new file mode 100644 (file)
index 0000000..13c9e04
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_ellen_bintree.h"
+
+namespace set {
+
+    CDSSTRESS_EllenBinTreeSet( Set_InsDel_string, run_test_extract, std::string, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_feldman_hashset.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_feldman_hashset.cpp
new file mode 100644 (file)
index 0000000..94f1d6d
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_feldman_hashset.h"
+
+namespace set {
+
+    CDSSTRESS_FeldmanHashSet_stdhash( Set_InsDel_string, run_test_extract, std::string, size_t )
+    CDSSTRESS_FeldmanHashSet_city( Set_InsDel_string, run_test_extract, std::string, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_michael.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_michael.cpp
new file mode 100644 (file)
index 0000000..d0c181b
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_michael.h"
+
+namespace set {
+
+    CDSSTRESS_MichaelSet( Set_InsDel_string_LF, run_test_extract, std::string, size_t )
+    CDSSTRESS_MichaelIterableSet( Set_InsDel_string_LF, run_test_extract, std::string, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_skip.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_skip.cpp
new file mode 100644 (file)
index 0000000..1b6a724
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_skip_list.h"
+
+namespace set {
+
+    CDSSTRESS_SkipListSet( Set_InsDel_string, run_test_extract, std::string, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_split.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_split.cpp
new file mode 100644 (file)
index 0000000..8d9ff71
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_split_list.h"
+
+namespace set {
+
+    CDSSTRESS_SplitListSet( Set_InsDel_string_LF, run_test_extract, std::string, size_t )
+    CDSSTRESS_SplitListIterableSet( Set_InsDel_string_LF, run_test_extract, std::string, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_std.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_std.cpp
new file mode 100644 (file)
index 0000000..b81f90b
--- /dev/null
@@ -0,0 +1,37 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_std.h"
+
+namespace set {
+    //CDSSTRESS_StdSet( Set_InsDel_string, run_test, std::string, size_t )
+} // namespace set
+
diff --git a/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_striped.cpp b/test/stress/sequential/sequential-set/insdel_string/set_insdel_string_striped.cpp
new file mode 100644 (file)
index 0000000..b1baa87
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_insdel_string.h"
+#include "set_type_striped.h"
+
+namespace set {
+
+    //CDSSTRESS_StripedSet( Set_InsDel_string_LF, run_test, std::string, size_t )
+
+} // namespace set
+
diff --git a/test/stress/sequential/sequential-set/iter_erase/CMakeLists.txt b/test/stress/sequential/sequential-set/iter_erase/CMakeLists.txt
new file mode 100644 (file)
index 0000000..0c68317
--- /dev/null
@@ -0,0 +1,19 @@
+set(PACKAGE_NAME stress-sequential-set-iter-erase)
+
+set(CDSSTRESS_SET_ITER_ERASE_SOURCES
+    ../../../main.cpp
+    set_iter_erase.cpp
+    set_iter_erase_feldman_hashset.cpp
+    set_iter_erase_michael.cpp
+    set_iter_erase_split.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_SET_ITER_ERASE_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
diff --git a/test/stress/sequential/sequential-set/iter_erase/set_iter_erase.cpp b/test/stress/sequential/sequential-set/iter_erase/set_iter_erase.cpp
new file mode 100644 (file)
index 0000000..e52a4c8
--- /dev/null
@@ -0,0 +1,116 @@
+/*
+    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.
+*/
+
+#include "set_iter_erase.h"
+
+namespace set {
+
+    size_t  Set_Iter_Del3::s_nSetSize = 5000;
+    size_t  Set_Iter_Del3::s_nInsThreadCount = 4;
+    size_t  Set_Iter_Del3::s_nDelThreadCount = 4;
+    size_t  Set_Iter_Del3::s_nExtractThreadCount = 4;
+    size_t  Set_Iter_Del3::s_nFindThreadCount = 2;
+    size_t  Set_Iter_Del3::s_nMaxLoadFactor = 4;
+    size_t  Set_Iter_Del3::s_nInsertPassCount = 1000;
+
+    size_t Set_Iter_Del3::s_nFeldmanSet_HeadBits = 8;
+    size_t Set_Iter_Del3::s_nFeldmanSet_ArrayBits = 8;
+
+    size_t Set_Iter_Del3::s_nLoadFactor = 1;
+    std::vector<size_t> Set_Iter_Del3::m_arrData;
+
+    void Set_Iter_Del3::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "map_iter_erase" );
+
+        s_nSetSize = cfg.get_size_t( "MapSize", s_nSetSize );
+        if ( s_nSetSize < 1000 )
+            s_nSetSize = 1000;
+
+        s_nInsThreadCount = cfg.get_size_t( "InsThreadCount", s_nInsThreadCount );
+        if ( s_nInsThreadCount == 0 )
+            s_nInsThreadCount = 1;
+
+        s_nDelThreadCount = cfg.get_size_t( "DelThreadCount", s_nDelThreadCount );
+        s_nExtractThreadCount = cfg.get_size_t( "ExtractThreadCount", s_nExtractThreadCount );
+        s_nFindThreadCount = cfg.get_size_t( "FindThreadCount", s_nFindThreadCount );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        s_nInsertPassCount = cfg.get_size_t( "PassCount", s_nInsertPassCount );
+        if ( s_nInsertPassCount == 0 )
+            s_nInsertPassCount = 1000;
+
+        s_nFeldmanSet_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanSet_HeadBits );
+        if ( s_nFeldmanSet_HeadBits == 0 )
+            s_nFeldmanSet_HeadBits = 8;
+
+        s_nFeldmanSet_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanSet_ArrayBits );
+        if ( s_nFeldmanSet_ArrayBits == 0 )
+            s_nFeldmanSet_ArrayBits = 8;
+
+        m_arrData.resize( s_nSetSize );
+        for ( size_t i = 0; i < s_nSetSize; ++i )
+            m_arrData[i] = i;
+        shuffle( m_arrData.begin(), m_arrData.end());
+    }
+
+    void Set_Iter_Del3::TearDownTestCase()
+    {
+        m_arrData.clear();
+    }
+
+    std::vector<size_t> Set_Iter_Del3_LF::get_load_factors()
+    {
+        cds_test::config const& cfg = get_config( "map_iter_erase" );
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        std::vector<size_t> lf;
+        for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 )
+            lf.push_back( n );
+
+        return lf;
+    }
+
+#ifdef CDSTEST_GTEST_INSTANTIATE_TEST_CASE_P_HAS_4TH_ARG
+    static std::string get_test_parameter_name( testing::TestParamInfo<size_t> const& p )
+    {
+        return std::to_string( p.param );
+    }
+    INSTANTIATE_TEST_CASE_P( a, Set_Iter_Del3_LF, ::testing::ValuesIn( Set_Iter_Del3_LF::get_load_factors()), get_test_parameter_name );
+#else
+    INSTANTIATE_TEST_CASE_P( a, Set_Iter_Del3_LF, ::testing::ValuesIn( Set_Iter_Del3_LF::get_load_factors()));
+#endif
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/iter_erase/set_iter_erase.h b/test/stress/sequential/sequential-set/iter_erase/set_iter_erase.h
new file mode 100644 (file)
index 0000000..1615311
--- /dev/null
@@ -0,0 +1,885 @@
+/*
+    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.
+*/
+
+#include "set_type.h"
+#include <cds/os/topology.h>
+
+namespace set {
+
+    struct key_thread
+    {
+        uint32_t  nKey;
+        uint16_t  nThread;
+
+        key_thread( size_t key, size_t threadNo )
+            : nKey( static_cast<uint32_t>(key))
+            , nThread( static_cast<uint16_t>(threadNo))
+        {}
+
+        key_thread()
+            : nKey()
+            , nThread()
+        {}
+    };
+
+    static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
+
+    typedef set_type_base<key_thread, size_t>::key_val     key_value_pair;
+
+    template <>
+    struct cmp<key_thread> {
+        int operator ()(key_thread const& k1, key_thread const& k2) const
+        {
+            if ( k1.nKey < k2.nKey )
+                return -1;
+            if ( k1.nKey > k2.nKey )
+                return 1;
+            if ( k1.nThread < k2.nThread )
+                return -1;
+            if ( k1.nThread > k2.nThread )
+                return 1;
+            return 0;
+        }
+        int operator ()(key_thread const& k1, size_t k2) const
+        {
+            if ( k1.nKey < k2 )
+                return -1;
+            if ( k1.nKey > k2 )
+                return 1;
+            return 0;
+        }
+        int operator ()(size_t k1, key_thread const& k2) const
+        {
+            if ( k1 < k2.nKey )
+                return -1;
+            if ( k1 > k2.nKey )
+                return 1;
+            return 0;
+        }
+    };
+
+    template <>
+    struct less<set::key_thread>
+    {
+        bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
+        {
+            if ( k1.nKey <= k2.nKey )
+                return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
+            return false;
+        }
+    };
+
+    template <>
+    struct hash<set::key_thread>
+    {
+        typedef size_t             result_type;
+        typedef set::key_thread    argument_type;
+
+        size_t operator()( set::key_thread const& k ) const
+        {
+            return std::hash<size_t>()(k.nKey);
+        }
+
+        size_t operator()( size_t k ) const
+        {
+            return std::hash<size_t>()(k);
+        }
+    };
+
+
+    class Set_Iter_Del3: public cds_test::stress_fixture
+    {
+    public:
+        static size_t s_nSetSize;              // max set size
+        static size_t s_nInsThreadCount;       // insert thread count
+        static size_t s_nDelThreadCount;       // delete thread count
+        static size_t s_nExtractThreadCount;   // extract thread count
+        static size_t s_nMaxLoadFactor;        // maximum load factor
+        static size_t s_nInsertPassCount;
+        static size_t s_nFindThreadCount;      // find thread count
+
+        static size_t s_nFeldmanSet_HeadBits;
+        static size_t s_nFeldmanSet_ArrayBits;
+
+        static size_t s_nLoadFactor;
+
+        static std::vector<size_t> m_arrData;
+
+        static void SetUpTestCase();
+        static void TearDownTestCase();
+
+        template <typename Pred>
+        static void prepare_array( std::vector<size_t>& arr, Pred pred )
+        {
+            arr.reserve( m_arrData.size());
+            for ( auto el : m_arrData ) {
+                if ( pred( el ))
+                    arr.push_back( el );
+            }
+            arr.resize( arr.size());
+            shuffle( arr.begin(), arr.end());
+        }
+
+    protected:
+        typedef key_thread  key_type;
+        typedef size_t      value_type;
+
+        atomics::atomic<size_t> m_nInsThreadCount;
+
+        enum {
+            inserter_thread,
+            deleter_thread,
+            extractor_thread,
+            find_thread
+        };
+
+
+        // Inserts keys from [0..N)
+        template <class Set>
+        class Inserter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            struct update_functor
+            {
+                template <typename Q>
+                void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
+                {}
+
+                void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
+                {}
+            };
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t ) -> bool { return true; } );
+                for ( size_t i = 0; i < m_arr.size(); ++i ) {
+                    if ( m_Set.insert( key_type( m_arr[i], id())))
+                        ++m_nInsertInitSuccess;
+                    else
+                        ++m_nInsertInitFailed;
+                }
+            }
+
+        public:
+            size_t  m_nInsertSuccess = 0;
+            size_t  m_nInsertFailed = 0;
+            size_t m_nInsertInitSuccess = 0;
+            size_t m_nInsertInitFailed = 0;
+
+            std::vector<size_t> m_arr;
+
+        public:
+            Inserter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, inserter_thread )
+                , m_Set( set )
+            {
+                init_data();
+            }
+
+            Inserter( Inserter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Inserter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
+
+                for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
+                    if ( nPass & 1 ) {
+                        // insert pass
+                        for ( auto el : m_arr ) {
+                            if ( el & 3 ) {
+                                if ( rSet.insert( key_type( el, id())))
+                                    ++m_nInsertSuccess;
+                                else
+                                    ++m_nInsertFailed;
+                            }
+                        }
+                    }
+                    else {
+                        // update pass
+                        for ( auto el : m_arr ) {
+                            if ( el & 3 ) {
+                                bool success;
+                                bool inserted;
+                                std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
+                                if ( success && inserted )
+                                    ++m_nInsertSuccess;
+                                else
+                                    ++m_nInsertFailed;
+                            }
+                        }
+                    }
+                }
+
+                fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
+                m_arr.resize( 0 );
+            }
+        };
+
+        struct key_equal {
+            bool operator()( key_type const& k1, key_type const& k2 ) const
+            {
+                return k1.nKey == k2.nKey;
+            }
+            bool operator()( size_t k1, key_type const& k2 ) const
+            {
+                return k1 == k2.nKey;
+            }
+            bool operator()( key_type const& k1, size_t k2 ) const
+            {
+                return k1.nKey == k2;
+            }
+            bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1.key, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, size_t k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( size_t k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+        };
+
+        struct key_less {
+            bool operator()( key_type const& k1, key_type const& k2 ) const
+            {
+                return k1.nKey < k2.nKey;
+            }
+            bool operator()( size_t k1, key_type const& k2 ) const
+            {
+                return k1 < k2.nKey;
+            }
+            bool operator()( key_type const& k1, size_t k2 ) const
+            {
+                return k1.nKey < k2;
+            }
+            bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1.key, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+            bool operator ()( key_value_pair const& k1, size_t k2 ) const
+            {
+                return operator()( k1.key, k2 );
+            }
+            bool operator ()( size_t k1, key_value_pair const& k2 ) const
+            {
+                return operator()( k1, k2.key );
+            }
+
+            typedef key_equal   equal_to;
+        };
+
+        // Deletes keys from [0..N)
+        template <class Set, typename Iterator>
+        class Deleter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+        public:
+            size_t  m_nDeleteSuccess = 0;
+            size_t  m_nDeleteFailed = 0;
+
+        public:
+            Deleter( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, deleter_thread )
+                , m_Set( set )
+            {}
+
+            Deleter( Deleter& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Deleter( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+
+                Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
+
+                do {
+                    auto itEnd = rSet.template get_end<Iterator>();
+                    for ( auto it = rSet.template get_begin<Iterator>(); it != itEnd; ++it ) {
+                        if ( it->key.nKey & 3 ) {
+                            if ( rSet.erase_at( it ))
+                                ++m_nDeleteSuccess;
+                            else
+                                ++m_nDeleteFailed;
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+            }
+        };
+
+        // Extracts keys from [0..N)
+        template <typename GC, class Set>
+        class Extractor: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+
+            std::vector<size_t> m_arr;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nExtractSuccess = 0;
+            size_t  m_nExtractFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extractor_thread )
+                , m_Set( set )
+            {
+                init_data();
+            }
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                typename Set::guarded_ptr gp;
+
+                Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
+                size_t const nInsThreadCount = s_nInsThreadCount;
+
+                do {
+                    if ( id() & 1 ) {
+                        for ( auto el : m_arr ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                gp = rSet.extract( key_type( el, k ));
+                                if ( gp )
+                                    ++m_nExtractSuccess;
+                                else
+                                    ++m_nExtractFailed;
+                                gp.release();
+                            }
+                        }
+                    }
+                    else {
+                        for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                            for ( auto el : m_arr ) {
+                                gp = rSet.extract( key_type( el, k ));
+                                if ( gp )
+                                    ++m_nExtractSuccess;
+                                else
+                                    ++m_nExtractFailed;
+                                gp.release();
+                            }
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+                m_arr.resize( 0 );
+            }
+        };
+
+        template <typename RCU, class Set>
+        class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&     m_Set;
+            std::vector<size_t> m_arr;
+
+            void init_data()
+            {
+                prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
+            }
+
+        public:
+            size_t  m_nExtractSuccess = 0;
+            size_t  m_nExtractFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, extractor_thread )
+                , m_Set( set )
+            {
+                init_data();
+            }
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Set& rSet = m_Set;
+                typename Set::exempt_ptr xp;
+
+                Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
+                size_t const nInsThreadCount = fixture.s_nInsThreadCount;
+
+                do {
+                    if ( id() & 1 ) {
+                        for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                            for ( auto el : m_arr ) {
+                                if ( Set::c_bExtractLockExternal ) {
+                                    typename Set::rcu_lock l;
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                else {
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                xp.release();
+                            }
+                        }
+                    }
+                    else {
+                        for ( auto el : m_arr ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( Set::c_bExtractLockExternal ) {
+                                    typename Set::rcu_lock l;
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                else {
+                                    xp = rSet.extract( key_type( el, k ));
+                                    if ( xp )
+                                        ++m_nExtractSuccess;
+                                    else
+                                        ++m_nExtractFailed;
+                                }
+                                xp.release();
+                            }
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+                m_arr.resize( 0 );
+            }
+        };
+
+        // Finds keys
+        template <class Set>
+        class Observer: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Set&                m_Set;
+
+        public:
+            size_t m_nFindEvenSuccess = 0;
+            size_t m_nFindEvenFailed = 0;
+            size_t m_nFindOddSuccess = 0;
+            size_t m_nFindOddFailed = 0;
+
+        public:
+            Observer( cds_test::thread_pool& pool, Set& set )
+                : base_class( pool, find_thread )
+                , m_Set( set )
+            {}
+
+            Observer( Observer& src )
+                : base_class( src )
+                , m_Set( src.m_Set )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Observer( *this );
+            }
+
+            virtual void test()
+            {
+                Set& set = m_Set;
+                Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
+                std::vector<size_t> const& arr = m_arrData;
+                size_t const nInsThreadCount = s_nInsThreadCount;
+
+                do {
+                    for ( size_t key : arr ) {
+                        if ( key & 3 ) {
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( set.contains( key_thread( key, k )))
+                                    ++m_nFindOddSuccess;
+                                else
+                                    ++m_nFindOddFailed;
+                            }
+                        }
+                        else {
+                            // that keys MUST be in the map
+                            for ( size_t k = 0; k < nInsThreadCount; ++k ) {
+                                if ( set.contains( key_thread( key, k )))
+                                    ++m_nFindEvenSuccess;
+                                else
+                                    ++m_nFindEvenFailed;
+                            }
+                        }
+                    }
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+            }
+        };
+
+    protected:
+        template <typename Iterator, class Set>
+        void do_test_with( Set& testSet )
+        {
+            typedef Inserter<Set> insert_thread;
+            typedef Deleter<Set, Iterator> delete_thread;
+            typedef Observer<Set> observer_thread;
+
+            m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
+            pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
+            if ( s_nFindThreadCount )
+                pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+                << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+                << std::make_pair( "find_thread_count", s_nFindThreadCount )
+                << std::make_pair( "set_size", s_nSetSize )
+                << std::make_pair( "pass_count", s_nInsertPassCount );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertInitFailed = 0;
+            size_t nInsertInitSuccess = 0;
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+
+            size_t nFindEvenSuccess = 0;
+            size_t nFindEvenFailed = 0;
+            size_t nFindOddSuccess = 0;
+            size_t nFindOddFailed = 0;
+
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case inserter_thread:
+                    {
+                        insert_thread& inserter = static_cast<insert_thread&>(thr);
+                        nInsertSuccess += inserter.m_nInsertSuccess;
+                        nInsertFailed += inserter.m_nInsertFailed;
+                        nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+                        nInsertInitFailed += inserter.m_nInsertInitFailed;
+                    }
+                    break;
+                case deleter_thread:
+                    {
+                        delete_thread& deleter = static_cast<delete_thread&>(thr);
+                        nDeleteSuccess += deleter.m_nDeleteSuccess;
+                        nDeleteFailed += deleter.m_nDeleteFailed;
+                    }
+                    break;
+                case find_thread:
+                    {
+                        observer_thread& observer = static_cast<observer_thread&>( thr );
+                        nFindEvenSuccess = observer.m_nFindEvenSuccess;
+                        nFindEvenFailed = observer.m_nFindEvenFailed;
+                        nFindOddSuccess = observer.m_nFindOddSuccess;
+                        nFindOddFailed = observer.m_nFindOddFailed;
+                    }
+                    break;
+                default:
+                    assert( false );
+                }
+            }
+
+            size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
+
+            EXPECT_EQ( nInsertInitFailed, 0u );
+            EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
+            EXPECT_EQ( nFindEvenFailed, 0u );
+            EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
+            EXPECT_LE( nInsertSuccess, nDeleteSuccess );
+
+            propout()
+                << std::make_pair( "insert_init_success", nInsertInitSuccess )
+                << std::make_pair( "insert_init_failed", nInsertInitFailed )
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "find_even_success", nFindEvenSuccess )
+                << std::make_pair( "find_even_failed", nFindEvenFailed )
+                << std::make_pair( "find_odd_success", nFindOddSuccess )
+                << std::make_pair( "find_odd_failed", nFindOddFailed );
+        }
+
+        template <typename Iterator, class Set>
+        void do_test_extract_with( Set& testSet )
+        {
+            typedef Inserter<Set> insert_thread;
+            typedef Deleter<Set, Iterator> delete_thread;
+            typedef Extractor< typename Set::gc, Set > extract_thread;
+            typedef Observer<Set> observer_thread;
+
+            m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
+            if ( s_nDelThreadCount )
+                pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
+            if ( s_nExtractThreadCount )
+                pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
+            if ( s_nFindThreadCount )
+                pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+                << std::make_pair( "delete_thread_count", s_nDelThreadCount )
+                << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
+                << std::make_pair( "find_thread_count", s_nFindThreadCount )
+                << std::make_pair( "set_size", s_nSetSize )
+                << std::make_pair( "pass_count", s_nInsertPassCount );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertInitFailed = 0;
+            size_t nInsertInitSuccess = 0;
+            size_t nInsertSuccess = 0;
+            size_t nInsertFailed = 0;
+            size_t nDeleteSuccess = 0;
+            size_t nDeleteFailed = 0;
+            size_t nExtractSuccess = 0;
+            size_t nExtractFailed = 0;
+
+            size_t nFindEvenSuccess = 0;
+            size_t nFindEvenFailed = 0;
+            size_t nFindOddSuccess = 0;
+            size_t nFindOddFailed = 0;
+
+            for ( size_t i = 0; i < pool.size(); ++i ) {
+                cds_test::thread& thr = pool.get( i );
+                switch ( thr.type()) {
+                case inserter_thread:
+                    {
+                        insert_thread& inserter = static_cast<insert_thread&>( thr );
+                        nInsertSuccess += inserter.m_nInsertSuccess;
+                        nInsertFailed += inserter.m_nInsertFailed;
+                        nInsertInitSuccess += inserter.m_nInsertInitSuccess;
+                        nInsertInitFailed += inserter.m_nInsertInitFailed;
+                    }
+                    break;
+                case deleter_thread:
+                    {
+                        delete_thread& deleter = static_cast<delete_thread&>(thr);
+                        nDeleteSuccess += deleter.m_nDeleteSuccess;
+                        nDeleteFailed += deleter.m_nDeleteFailed;
+                    }
+                    break;
+                case extractor_thread:
+                    {
+                        extract_thread& extractor = static_cast<extract_thread&>(thr);
+                        nExtractSuccess += extractor.m_nExtractSuccess;
+                        nExtractFailed += extractor.m_nExtractFailed;
+                    }
+                    break;
+                case find_thread:
+                    {
+                        observer_thread& observer = static_cast<observer_thread&>( thr );
+                        nFindEvenSuccess = observer.m_nFindEvenSuccess;
+                        nFindEvenFailed = observer.m_nFindEvenFailed;
+                        nFindOddSuccess = observer.m_nFindOddSuccess;
+                        nFindOddFailed = observer.m_nFindOddFailed;
+                    }
+                    break;
+                default:
+                    assert( false );
+                }
+            }
+
+            size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
+
+            EXPECT_EQ( nInsertInitFailed, 0u );
+            EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
+            EXPECT_EQ( nFindEvenFailed, 0u );
+            EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
+            EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
+
+            propout()
+                << std::make_pair( "insert_init_success", nInsertInitSuccess )
+                << std::make_pair( "insert_init_failed", nInsertInitFailed )
+                << std::make_pair( "insert_success", nInsertSuccess )
+                << std::make_pair( "insert_failed", nInsertFailed )
+                << std::make_pair( "delete_success", nDeleteSuccess )
+                << std::make_pair( "delete_failed", nDeleteFailed )
+                << std::make_pair( "extract_success", nExtractSuccess )
+                << std::make_pair( "extract_failed", nExtractFailed )
+                << std::make_pair( "find_even_success", nFindEvenSuccess )
+                << std::make_pair( "find_even_failed", nFindEvenFailed )
+                << std::make_pair( "find_odd_success", nFindOddSuccess )
+                << std::make_pair( "find_odd_failed", nFindOddFailed );
+        }
+
+        template <typename Set>
+        void analyze( Set& testSet )
+        {
+            // All even keys must be in the set
+            {
+                for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
+                    for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
+                        EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
+                    }
+                }
+            }
+
+            check_before_clear( testSet );
+
+            testSet.clear();
+            EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
+
+            additional_check( testSet );
+            print_stat( propout(), testSet );
+            additional_cleanup( testSet );
+        }
+
+        template <class Set, typename Iterator=typename Set::iterator>
+        void run_test()
+        {
+            static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
+
+            Set  testSet( *this );
+            do_test_with<Iterator>( testSet );
+            analyze( testSet );
+        }
+
+        template <class Set, typename Iterator=typename Set::iterator>
+        void run_test_extract()
+        {
+            static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
+
+            Set  testSet( *this );
+            do_test_extract_with<Iterator>( testSet );
+            analyze( testSet );
+        }
+
+        template <class Set>
+        void run_feldman();
+    };
+
+    class Set_Iter_Del3_reverse: public Set_Iter_Del3
+    {
+    public:
+        template <class Set>
+        void run_feldman();
+    };
+
+
+    class Set_Iter_Del3_LF: public Set_Iter_Del3
+        , public ::testing::WithParamInterface<size_t>
+    {
+    public:
+        template <class Set>
+        void run_test()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_Iter_Del3::run_test<Set>();
+        }
+
+        template <class Set>
+        void run_test_extract()
+        {
+            s_nLoadFactor = GetParam();
+            propout() << std::make_pair( "load_factor", s_nLoadFactor );
+            Set_Iter_Del3::run_test_extract<Set>();
+        }
+
+        static std::vector<size_t> get_load_factors();
+    };
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/iter_erase/set_iter_erase_feldman_hashset.cpp b/test/stress/sequential/sequential-set/iter_erase/set_iter_erase_feldman_hashset.cpp
new file mode 100644 (file)
index 0000000..5dfb129
--- /dev/null
@@ -0,0 +1,64 @@
+/*
+    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.
+*/
+
+#include "set_iter_erase.h"
+#include "set_type_feldman_hashset.h"
+
+namespace set {
+
+    template <class Set>
+    void Set_Iter_Del3::run_feldman()
+    {
+        typedef typename Set::traits original_traits;
+        struct traits: public original_traits {
+            enum { hash_size = sizeof( uint32_t ) + sizeof( uint16_t ) };
+        };
+        typedef typename Set::template rebind_traits< traits >::result set_type;
+
+        run_test_extract<set_type>();
+    }
+
+    template <class Set>
+    void Set_Iter_Del3_reverse::run_feldman()
+    {
+        typedef typename Set::traits original_traits;
+        struct traits: public original_traits {
+            enum { hash_size = sizeof( uint32_t ) + sizeof( uint16_t ) };
+        };
+        typedef typename Set::template rebind_traits< traits >::result set_type;
+
+        run_test_extract<set_type, typename set_type::reverse_iterator>();
+    }
+
+    //TODO: add erase_at() to FeldmanHashSet<RCU>
+    CDSSTRESS_FeldmanHashSet_fixed_HP( Set_Iter_Del3, run_feldman, key_thread, size_t )
+    CDSSTRESS_FeldmanHashSet_fixed_HP( Set_Iter_Del3_reverse, run_feldman, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/iter_erase/set_iter_erase_michael.cpp b/test/stress/sequential/sequential-set/iter_erase/set_iter_erase_michael.cpp
new file mode 100644 (file)
index 0000000..3a69c96
--- /dev/null
@@ -0,0 +1,39 @@
+/*
+    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.
+*/
+
+#include "set_iter_erase.h"
+#include "set_type_michael.h"
+
+namespace set {
+
+    // Test is too long
+    //CDSSTRESS_MichaelIterableSet( Set_Iter_Del3_LF, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/iter_erase/set_iter_erase_split.cpp b/test/stress/sequential/sequential-set/iter_erase/set_iter_erase_split.cpp
new file mode 100644 (file)
index 0000000..235a02c
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+    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.
+*/
+
+#include "set_iter_erase.h"
+#include "set_type_split_list.h"
+
+namespace set {
+    // Too long
+    //CDSSTRESS_SplitListIterableSet( Set_Iter_Del3_LF, run_test_extract, key_thread, size_t )
+
+} // namespace set
diff --git a/test/stress/sequential/sequential-set/iteration/CMakeLists.txt b/test/stress/sequential/sequential-set/iteration/CMakeLists.txt
new file mode 100644 (file)
index 0000000..0adcbd5
--- /dev/null
@@ -0,0 +1,18 @@
+set(PACKAGE_NAME stress-sequential-set-iteration)
+
+set(CDSSTRESS_SET_ITERATION_SOURCES
+    ../../../main.cpp
+    set_iteration.cpp
+    set_iteration_feldman_hashset.cpp
+    set_iteration_michael.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_SET_ITERATION_SOURCES})
+target_link_libraries(${PACKAGE_NAME} ${CDS_TEST_LIBRARIES} ${CDSSTRESS_FRAMEWORK_LIBRARY})
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
diff --git a/test/stress/sequential/sequential-set/iteration/set_iteration.cpp b/test/stress/sequential/sequential-set/iteration/set_iteration.cpp
new file mode 100644 (file)
index 0000000..8012b26
--- /dev/null
@@ -0,0 +1,126 @@
+/*
+    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.
+*/
+
+#include "set_iteration.h"
+
+namespace set {
+
+    size_t Set_Iteration::s_nSetSize = 1000000;      // set size
+    size_t Set_Iteration::s_nInsertThreadCount = 4;  // count of insertion thread
+    size_t Set_Iteration::s_nDeleteThreadCount = 4;  // count of deletion thread
+    size_t Set_Iteration::s_nThreadPassCount = 4;    // pass count for each thread
+    size_t Set_Iteration::s_nMaxLoadFactor = 8;      // maximum load factor
+
+    size_t Set_Iteration::s_nCuckooInitialSize = 1024;// initial size for CuckooSet
+    size_t Set_Iteration::s_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
+    size_t Set_Iteration::s_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
+
+    size_t Set_Iteration::s_nFeldmanSet_HeadBits = 10;
+    size_t Set_Iteration::s_nFeldmanSet_ArrayBits = 4;
+
+    size_t Set_Iteration::s_nLoadFactor = 1;
+    std::vector<std::string> Set_Iteration::m_arrString;
+
+    void Set_Iteration::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "map_insdel_string" );
+
+        s_nSetSize = cfg.get_size_t( "MapSize", s_nSetSize );
+        if ( s_nSetSize < 1000 )
+            s_nSetSize = 1000;
+
+        s_nInsertThreadCount = cfg.get_size_t( "InsertThreadCount", s_nInsertThreadCount );
+        if ( s_nInsertThreadCount == 0 )
+            s_nInsertThreadCount = 2;
+
+        s_nDeleteThreadCount = cfg.get_size_t( "DeleteThreadCount", s_nDeleteThreadCount );
+        if ( s_nDeleteThreadCount == 0 )
+            s_nDeleteThreadCount = 2;
+
+        s_nThreadPassCount = cfg.get_size_t( "ThreadPassCount", s_nThreadPassCount );
+        if ( s_nThreadPassCount == 0 )
+            s_nThreadPassCount = 4;
+
+        s_nMaxLoadFactor = cfg.get_size_t( "MaxLoadFactor", s_nMaxLoadFactor );
+        if ( s_nMaxLoadFactor == 0 )
+            s_nMaxLoadFactor = 1;
+
+        s_nCuckooInitialSize = cfg.get_size_t( "CuckooInitialSize", s_nCuckooInitialSize );
+        if ( s_nCuckooInitialSize < 256 )
+            s_nCuckooInitialSize = 256;
+
+        s_nCuckooProbesetSize = cfg.get_size_t( "CuckooProbesetSize", s_nCuckooProbesetSize );
+        if ( s_nCuckooProbesetSize < 8 )
+            s_nCuckooProbesetSize = 8;
+
+        s_nCuckooProbesetThreshold = cfg.get_size_t( "CuckooProbesetThreshold", s_nCuckooProbesetThreshold );
+
+        s_nFeldmanSet_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanSet_HeadBits );
+        if ( s_nFeldmanSet_HeadBits == 0 )
+            s_nFeldmanSet_HeadBits = 2;
+
+        s_nFeldmanSet_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanSet_ArrayBits );
+        if ( s_nFeldmanSet_ArrayBits == 0 )
+            s_nFeldmanSet_ArrayBits = 2;
+
+