From f6b0b036db411b1ca130f7ff3549463018572ec7 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 11 Mar 2017 19:58:31 +0300 Subject: [PATCH] Added stress-set-iter-erase test for testing erase_at() - erasing by iterator --- .gitignore | 2 - projects/Win/vc14/cds.sln | 19 + .../Win/vc14/stress-set-iter-erase.vcxproj | 253 +++++ projects/Win/vc141/cds.sln | 19 + .../Win/vc141/stress-set-iter-erase.vcxproj | 253 +++++ test/stress/set/CMakeLists.txt | 2 + test/stress/set/iter_erase/CMakeLists.txt | 19 + test/stress/set/iter_erase/set_iter_erase.cpp | 123 +++ test/stress/set/iter_erase/set_iter_erase.h | 893 ++++++++++++++++++ .../set_iter_erase_feldman_hashset.cpp | 64 ++ .../set/iter_erase/set_iter_erase_michael.cpp | 40 + .../set/iter_erase/set_iter_erase_split.cpp | 39 + test/stress/set/set_type_feldman_hashset.h | 30 +- 13 files changed, 1753 insertions(+), 3 deletions(-) create mode 100644 projects/Win/vc14/stress-set-iter-erase.vcxproj create mode 100644 projects/Win/vc141/stress-set-iter-erase.vcxproj create mode 100644 test/stress/set/iter_erase/CMakeLists.txt create mode 100644 test/stress/set/iter_erase/set_iter_erase.cpp create mode 100644 test/stress/set/iter_erase/set_iter_erase.h create mode 100644 test/stress/set/iter_erase/set_iter_erase_feldman_hashset.cpp create mode 100644 test/stress/set/iter_erase/set_iter_erase_michael.cpp create mode 100644 test/stress/set/iter_erase/set_iter_erase_split.cpp diff --git a/.gitignore b/.gitignore index ec23c2f4..75c0f0d0 100644 --- a/.gitignore +++ b/.gitignore @@ -1,9 +1,7 @@ /doc /sandbox -/tests/cppunit/*.o *.o *.d -/tests/data/dictionary.txt /bin /obj /projects/Win/vc14/cds.sdf diff --git a/projects/Win/vc14/cds.sln b/projects/Win/vc14/cds.sln index 3f203576..dab5f4aa 100644 --- a/projects/Win/vc14/cds.sln +++ b/projects/Win/vc14/cds.sln @@ -413,6 +413,12 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-map-minmax", "stress {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239} EndProjectSection EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-set-iter-erase", "stress-set-iter-erase.vcxproj", "{A717715D-CA08-4111-8A0E-B69A6DE3FF38}" + ProjectSection(ProjectDependencies) = postProject + {79A6845E-85BF-4000-94FF-9DF2473460D4} = {79A6845E-85BF-4000-94FF-9DF2473460D4} + {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239} + EndProjectSection +EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|Win32 = Debug|Win32 @@ -1179,6 +1185,18 @@ Global {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|Win32.Build.0 = Release|Win32 {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|x64.ActiveCfg = Release|x64 {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|x64.Build.0 = Release|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|Win32.ActiveCfg = Debug|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|Win32.Build.0 = Debug|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|x64.ActiveCfg = Debug|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|x64.Build.0 = Debug|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|Win32.ActiveCfg = DebugVLD|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|Win32.Build.0 = DebugVLD|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|x64.ActiveCfg = DebugVLD|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|x64.Build.0 = DebugVLD|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|Win32.ActiveCfg = Release|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|Win32.Build.0 = Release|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|x64.ActiveCfg = Release|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|x64.Build.0 = Release|x64 EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE @@ -1258,6 +1276,7 @@ Global {729E28BB-F36F-4462-8434-9C252C286525} = {7D3EE35B-185D-40B5-88C2-7F9933426978} {E91A1938-BB89-4676-9C9F-69AA697CB488} = {0D83E8C7-97D1-4BA1-928A-6846E7089652} {A0BC5155-F91B-4F89-B775-BB09A54EDB73} = {7D3EE35B-185D-40B5-88C2-7F9933426978} + {A717715D-CA08-4111-8A0E-B69A6DE3FF38} = {0D83E8C7-97D1-4BA1-928A-6846E7089652} EndGlobalSection GlobalSection(DPCodeReviewSolutionGUID) = preSolution DPCodeReviewSolutionGUID = {00000000-0000-0000-0000-000000000000} diff --git a/projects/Win/vc14/stress-set-iter-erase.vcxproj b/projects/Win/vc14/stress-set-iter-erase.vcxproj new file mode 100644 index 00000000..178b9edc --- /dev/null +++ b/projects/Win/vc14/stress-set-iter-erase.vcxproj @@ -0,0 +1,253 @@ + + + + + DebugVLD + Win32 + + + DebugVLD + x64 + + + Debug + Win32 + + + Release + Win32 + + + Debug + x64 + + + Release + x64 + + + + + + + + + + + + + + + + + {A717715D-CA08-4111-8A0E-B69A6DE3FF38} + Win32Proj + stress_set_iter_erase + 8.1 + stress-set-iter-erase + + + + Application + true + v140 + Unicode + + + Application + true + v140 + Unicode + + + Application + false + v140 + true + Unicode + + + Application + true + v140 + Unicode + + + Application + true + v140 + Unicode + + + Application + false + v140 + true + Unicode + + + + + + + + + + + + + + + + + + + + + + + + + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + false + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + + + false + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + Level3 + NotUsing + MaxSpeed + true + true + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + true + true + true + $(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtest.lib;stress-framework.lib;%(AdditionalDependencies) + + + + + Level3 + NotUsing + MaxSpeed + true + true + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + true + true + true + $(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtest.lib;stress-framework.lib;%(AdditionalDependencies) + + + + + + \ No newline at end of file diff --git a/projects/Win/vc141/cds.sln b/projects/Win/vc141/cds.sln index c4726b81..5224c9d1 100644 --- a/projects/Win/vc141/cds.sln +++ b/projects/Win/vc141/cds.sln @@ -413,6 +413,12 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-map-minmax", "stress {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239} EndProjectSection EndProject +Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-set-iter-erase", "stress-set-iter-erase.vcxproj", "{A717715D-CA08-4111-8A0E-B69A6DE3FF38}" + ProjectSection(ProjectDependencies) = postProject + {A34CED07-A442-4FA1-81C4-F8B9CD3C832B} = {A34CED07-A442-4FA1-81C4-F8B9CD3C832B} + {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239} + EndProjectSection +EndProject Global GlobalSection(SolutionConfigurationPlatforms) = preSolution Debug|Win32 = Debug|Win32 @@ -1179,6 +1185,18 @@ Global {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|Win32.Build.0 = Release|Win32 {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|x64.ActiveCfg = Release|x64 {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|x64.Build.0 = Release|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|Win32.ActiveCfg = Debug|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|Win32.Build.0 = Debug|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|x64.ActiveCfg = Debug|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Debug|x64.Build.0 = Debug|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|Win32.ActiveCfg = DebugVLD|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|Win32.Build.0 = DebugVLD|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|x64.ActiveCfg = DebugVLD|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.DebugVLD|x64.Build.0 = DebugVLD|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|Win32.ActiveCfg = Release|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|Win32.Build.0 = Release|Win32 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|x64.ActiveCfg = Release|x64 + {A717715D-CA08-4111-8A0E-B69A6DE3FF38}.Release|x64.Build.0 = Release|x64 EndGlobalSection GlobalSection(SolutionProperties) = preSolution HideSolutionNode = FALSE @@ -1258,6 +1276,7 @@ Global {729E28BB-F36F-4462-8434-9C252C286525} = {7D3EE35B-185D-40B5-88C2-7F9933426978} {E91A1938-BB89-4676-9C9F-69AA697CB488} = {0D83E8C7-97D1-4BA1-928A-6846E7089652} {A0BC5155-F91B-4F89-B775-BB09A54EDB73} = {7D3EE35B-185D-40B5-88C2-7F9933426978} + {A717715D-CA08-4111-8A0E-B69A6DE3FF38} = {0D83E8C7-97D1-4BA1-928A-6846E7089652} EndGlobalSection GlobalSection(DPCodeReviewSolutionGUID) = preSolution DPCodeReviewSolutionGUID = {00000000-0000-0000-0000-000000000000} diff --git a/projects/Win/vc141/stress-set-iter-erase.vcxproj b/projects/Win/vc141/stress-set-iter-erase.vcxproj new file mode 100644 index 00000000..d9c25593 --- /dev/null +++ b/projects/Win/vc141/stress-set-iter-erase.vcxproj @@ -0,0 +1,253 @@ + + + + + DebugVLD + Win32 + + + DebugVLD + x64 + + + Debug + Win32 + + + Release + Win32 + + + Debug + x64 + + + Release + x64 + + + + + + + + + + + + + + + + + {A717715D-CA08-4111-8A0E-B69A6DE3FF38} + Win32Proj + stress_set_iter_erase + 8.1 + stress-set-iter-erase + + + + Application + true + v141 + Unicode + + + Application + true + v141 + Unicode + + + Application + false + v141 + true + Unicode + + + Application + true + v141 + Unicode + + + Application + true + v141 + Unicode + + + Application + false + v141 + true + Unicode + + + + + + + + + + + + + + + + + + + + + + + + + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + true + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + $(ProjectName)_d + + + false + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + + + false + $(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\ + $(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\ + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + NotUsing + Level3 + Disabled + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;_DEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + DebugFastLink + $(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies) + + + + + Level3 + NotUsing + MaxSpeed + true + true + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + true + true + true + $(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtest.lib;stress-framework.lib;%(AdditionalDependencies) + + + + + Level3 + NotUsing + MaxSpeed + true + true + _ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;NDEBUG;_CONSOLE;%(PreprocessorDefinitions) + $(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\set;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories) + /bigobj %(AdditionalOptions) + + + Console + true + true + true + $(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir) + gtest.lib;stress-framework.lib;%(AdditionalDependencies) + + + + + + \ No newline at end of file diff --git a/test/stress/set/CMakeLists.txt b/test/stress/set/CMakeLists.txt index 3f326fa9..e8a618e9 100644 --- a/test/stress/set/CMakeLists.txt +++ b/test/stress/set/CMakeLists.txt @@ -7,6 +7,7 @@ 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-set DEPENDS @@ -16,4 +17,5 @@ add_custom_target( stress-set stress-set-insdel-func stress-set-insdel-string stress-set-iteration + stress-set-iter-erase ) diff --git a/test/stress/set/iter_erase/CMakeLists.txt b/test/stress/set/iter_erase/CMakeLists.txt new file mode 100644 index 00000000..4176d713 --- /dev/null +++ b/test/stress/set/iter_erase/CMakeLists.txt @@ -0,0 +1,19 @@ +set(PACKAGE_NAME stress-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}) + +add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH}) \ No newline at end of file diff --git a/test/stress/set/iter_erase/set_iter_erase.cpp b/test/stress/set/iter_erase/set_iter_erase.cpp new file mode 100644 index 00000000..79874e8e --- /dev/null +++ b/test/stress/set/iter_erase/set_iter_erase.cpp @@ -0,0 +1,123 @@ +/* + 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 = 1000000; + 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 = 8; + size_t Set_Iter_Del3::s_nInsertPassCount = 100; + + size_t Set_Iter_Del3::s_nCuckooInitialSize = 1024; + size_t Set_Iter_Del3::s_nCuckooProbesetSize = 16; + size_t Set_Iter_Del3::s_nCuckooProbesetThreshold = 0; + + size_t Set_Iter_Del3::s_nFeldmanSet_HeadBits = 10; + size_t Set_Iter_Del3::s_nFeldmanSet_ArrayBits = 4; + + + size_t Set_Iter_Del3::s_nLoadFactor = 1; + std::vector Set_Iter_Del3::m_arrData; + + void Set_Iter_Del3::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_Iter_Del3::TearDownTestCase() + { + m_arrData.clear(); + } + + std::vector Set_Iter_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 lf; + for ( size_t n = 1; n <= s_nMaxLoadFactor; n *= 2 ) + lf.push_back( n ); + + return lf; + } + + INSTANTIATE_TEST_CASE_P( a, Set_Iter_Del3_LF, ::testing::ValuesIn( Set_Iter_Del3_LF::get_load_factors())); +} // namespace set diff --git a/test/stress/set/iter_erase/set_iter_erase.h b/test/stress/set/iter_erase/set_iter_erase.h new file mode 100644 index 00000000..5ab5acfe --- /dev/null +++ b/test/stress/set/iter_erase/set_iter_erase.h @@ -0,0 +1,893 @@ +/* + 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 + +namespace set { + + struct key_thread + { + uint32_t nKey; + uint16_t nThread; + + key_thread( size_t key, size_t threadNo ) + : nKey( static_cast(key)) + , nThread( static_cast(threadNo)) + {} + + key_thread() + : nKey() + , nThread() + {} + }; + + static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch"); + + typedef set_type_base::key_val key_value_pair; + + template <> + struct cmp { + 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 + { + 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 + { + typedef size_t result_type; + typedef set::key_thread argument_type; + + size_t operator()( set::key_thread const& k ) const + { + return std::hash()(k.nKey); + } + + size_t operator()( size_t k ) const + { + return std::hash()(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_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 m_arrData; + + static void SetUpTestCase(); + static void TearDownTestCase(); + + template + static void prepare_array( std::vector& 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 m_nInsThreadCount; + + enum { + inserter_thread, + deleter_thread, + extractor_thread, + find_thread + }; + + + // Inserts keys from [0..N) + template + class Inserter: public cds_test::thread + { + typedef cds_test::thread base_class; + Set& m_Set; + + struct update_functor + { + template + 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 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(); + + 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 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; + + size_t const nInsThreadCount = s_nInsThreadCount; + Set_Iter_Del3& fixture = pool().template fixture(); + + do { + auto itEnd = rSet.get_end(); + for ( auto it = rSet.get_begin(); 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 + class Extractor: public cds_test::thread + { + typedef cds_test::thread base_class; + Set& m_Set; + + std::vector 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(); + 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 + class Extractor< cds::urcu::gc, Set >: public cds_test::thread + { + typedef cds_test::thread base_class; + Set& m_Set; + std::vector 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(); + 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 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(); + std::vector 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 + void do_test_with( Set& testSet ) + { + typedef Inserter insert_thread; + typedef Deleter delete_thread; + typedef Observer 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(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(thr); + nDeleteSuccess += deleter.m_nDeleteSuccess; + nDeleteFailed += deleter.m_nDeleteFailed; + } + break; + case find_thread: + { + observer_thread& observer = static_cast( 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 + void do_test_extract_with( Set& testSet ) + { + typedef Inserter insert_thread; + typedef Deleter delete_thread; + typedef Extractor< typename Set::gc, Set > extract_thread; + typedef Observer 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( 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(thr); + nDeleteSuccess += deleter.m_nDeleteSuccess; + nDeleteFailed += deleter.m_nDeleteFailed; + } + break; + case extractor_thread: + { + extract_thread& extractor = static_cast(thr); + nExtractSuccess += extractor.m_nExtractSuccess; + nExtractFailed += extractor.m_nExtractFailed; + } + break; + case find_thread: + { + observer_thread& observer = static_cast( 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 + 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 + 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 + 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 + void run_feldman(); + + template + void run_feldman_reverse(); + }; + + class Set_Iter_Del3_reverse: public Set_Iter_Del3 + { + public: + template + void run_feldman(); + }; + + + class Set_Iter_Del3_LF: public Set_Iter_Del3 + , public ::testing::WithParamInterface + { + public: + template + void run_test() + { + s_nLoadFactor = GetParam(); + propout() << std::make_pair( "load_factor", s_nLoadFactor ); + Set_Iter_Del3::run_test(); + } + + template + void run_test_extract() + { + s_nLoadFactor = GetParam(); + propout() << std::make_pair( "load_factor", s_nLoadFactor ); + Set_Iter_Del3::run_test_extract(); + } + + static std::vector get_load_factors(); + }; + +} // namespace set diff --git a/test/stress/set/iter_erase/set_iter_erase_feldman_hashset.cpp b/test/stress/set/iter_erase/set_iter_erase_feldman_hashset.cpp new file mode 100644 index 00000000..5dfb1295 --- /dev/null +++ b/test/stress/set/iter_erase/set_iter_erase_feldman_hashset.cpp @@ -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 + 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(); + } + + template + 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(); + } + + //TODO: add erase_at() to FeldmanHashSet + 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/set/iter_erase/set_iter_erase_michael.cpp b/test/stress/set/iter_erase/set_iter_erase_michael.cpp new file mode 100644 index 00000000..e0e88033 --- /dev/null +++ b/test/stress/set/iter_erase/set_iter_erase_michael.cpp @@ -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_iter_erase.h" +#include "set_type_michael.h" + +namespace set { + //TODO: add erase_at() to IterableList and MichaelHashSet +#if 0 + CDSSTRESS_MichaelIterableSet( Set_Iter_Del3_LF, run_test_extract, key_thread, size_t ) +#endif + +} // namespace set diff --git a/test/stress/set/iter_erase/set_iter_erase_split.cpp b/test/stress/set/iter_erase/set_iter_erase_split.cpp new file mode 100644 index 00000000..d67b7b50 --- /dev/null +++ b/test/stress/set/iter_erase/set_iter_erase_split.cpp @@ -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_split_list.h" + +namespace set { + //TODO: Add erase_at to IterableList and SplitList based on it +#if 0 + CDSSTRESS_SplitListIterableSet( Set_Iter_Del3_LF, run_test_extract, key_thread, size_t ) +#endif +} // namespace set diff --git a/test/stress/set/set_type_feldman_hashset.h b/test/stress/set/set_type_feldman_hashset.h index 40747d3d..c88b4c0b 100644 --- a/test/stress/set/set_type_feldman_hashset.h +++ b/test/stress/set/set_type_feldman_hashset.h @@ -47,7 +47,7 @@ namespace set { { typedef cc::FeldmanHashSet< GC, T, Traits > base_class; - template + template struct get_extracted_ptr { typedef typename base_class::guarded_ptr extracted_ptr; @@ -97,6 +97,34 @@ namespace set { return base_class::contains( hasher()(key)); } + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_begin() + { + return base_class::begin(); + } + + template + typename std::enable_if< std::is_same< Iterator, typename base_class::iterator>::value, Iterator>::type + get_end() + { + return base_class::end(); + } + + template + typename std::enable_if< std::is_same< Iterator, typename base_class::reverse_iterator>::value, Iterator>::type + get_begin() + { + return base_class::rbegin(); + } + + template + typename std::enable_if< std::is_same< Iterator, typename base_class::reverse_iterator>::value, Iterator>::type + get_end() + { + return base_class::rend(); + } + // for testing static CDS_CONSTEXPR bool const c_bExtractSupported = true; static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false; -- 2.34.1