Fixed bug in BronsonAVLTreeMap::extract_min()/extract_max()/clear()
authorkhizmax <libcds.dev@gmail.com>
Mon, 6 Feb 2017 18:54:57 +0000 (21:54 +0300)
committerkhizmax <libcds.dev@gmail.com>
Mon, 6 Feb 2017 18:54:57 +0000 (21:54 +0300)
Added map-minmax stress test

17 files changed:
change.log
projects/Win/vc14/cds.sln
projects/Win/vc14/stress-map-minmax.vcxproj [new file with mode: 0644]
test/stress/data/test-debug.conf
test/stress/data/test-express-x86.conf
test/stress/data/test-express.conf
test/stress/data/test.conf
test/stress/map/CMakeLists.txt
test/stress/map/map_type_bronson_avltree.h
test/stress/map/map_type_ellen_bintree.h
test/stress/map/map_type_skip_list.h
test/stress/map/minmax/CMakeLists.txt [new file with mode: 0644]
test/stress/map/minmax/map_minmax.cpp [new file with mode: 0644]
test/stress/map/minmax/map_minmax.h [new file with mode: 0644]
test/stress/map/minmax/map_minmax_bronsonavltree.cpp [new file with mode: 0644]
test/stress/map/minmax/map_minmax_ellentree.cpp [new file with mode: 0644]
test/stress/map/minmax/map_minmax_skip.cpp [new file with mode: 0644]

index e2dd7dc..12d91f7 100644 (file)
@@ -13,6 +13,7 @@
       External API of gc::DHP class is changed: now only initial count 
       of hazard pointers can be specified in the constructor. Like new gc::HP,
       the new gc::DHP supports an external allocator.
+    - Fixed a bug in BronsonAVLTreeMap::extract_min()/extract_max()/clear().
     - Added more flat-combining queue tests, thanks to Marsel Galimullin.
     - Changed cmake scripts to support MacOS and ARMv7/ARMv8 (64 bit),
       thanks to Michail Komarov (https://github.com/Nemo1369)
index c176115..4734338 100644 (file)
@@ -406,6 +406,8 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-set-del3", "stress-s
                {408FE9BC-44F0-4E6A-89FA-D6F952584239} = {408FE9BC-44F0-4E6A-89FA-D6F952584239}\r
        EndProjectSection\r
 EndProject\r
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "stress-map-minmax", "stress-map-minmax.vcxproj", "{A0BC5155-F91B-4F89-B775-BB09A54EDB73}"\r
+EndProject\r
 Global\r
        GlobalSection(SolutionConfigurationPlatforms) = preSolution\r
                Debug|Win32 = Debug|Win32\r
@@ -1160,6 +1162,18 @@ Global
                {E91A1938-BB89-4676-9C9F-69AA697CB488}.Release|Win32.Build.0 = Release|Win32\r
                {E91A1938-BB89-4676-9C9F-69AA697CB488}.Release|x64.ActiveCfg = Release|x64\r
                {E91A1938-BB89-4676-9C9F-69AA697CB488}.Release|x64.Build.0 = Release|x64\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Debug|Win32.ActiveCfg = Debug|Win32\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Debug|Win32.Build.0 = Debug|Win32\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Debug|x64.ActiveCfg = Debug|x64\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Debug|x64.Build.0 = Debug|x64\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.DebugVLD|Win32.ActiveCfg = DebugVLD|Win32\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.DebugVLD|Win32.Build.0 = DebugVLD|Win32\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.DebugVLD|x64.ActiveCfg = DebugVLD|x64\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.DebugVLD|x64.Build.0 = DebugVLD|x64\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|Win32.ActiveCfg = Release|Win32\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|Win32.Build.0 = Release|Win32\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|x64.ActiveCfg = Release|x64\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73}.Release|x64.Build.0 = Release|x64\r
        EndGlobalSection\r
        GlobalSection(SolutionProperties) = preSolution\r
                HideSolutionNode = FALSE\r
@@ -1238,6 +1252,7 @@ Global
                {31977D29-25C2-4FEC-9176-15247A15A9B4} = {810490B7-31E5-49AE-8455-CAF99A9658B6}\r
                {729E28BB-F36F-4462-8434-9C252C286525} = {7D3EE35B-185D-40B5-88C2-7F9933426978}\r
                {E91A1938-BB89-4676-9C9F-69AA697CB488} = {0D83E8C7-97D1-4BA1-928A-6846E7089652}\r
+               {A0BC5155-F91B-4F89-B775-BB09A54EDB73} = {7D3EE35B-185D-40B5-88C2-7F9933426978}\r
        EndGlobalSection\r
        GlobalSection(DPCodeReviewSolutionGUID) = preSolution\r
                DPCodeReviewSolutionGUID = {00000000-0000-0000-0000-000000000000}\r
diff --git a/projects/Win/vc14/stress-map-minmax.vcxproj b/projects/Win/vc14/stress-map-minmax.vcxproj
new file mode 100644 (file)
index 0000000..f9f6002
--- /dev/null
@@ -0,0 +1,253 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <ItemGroup Label="ProjectConfigurations">
+    <ProjectConfiguration Include="DebugVLD|Win32">
+      <Configuration>DebugVLD</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="DebugVLD|x64">
+      <Configuration>DebugVLD</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Debug|Win32">
+      <Configuration>Debug</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Release|Win32">
+      <Configuration>Release</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Debug|x64">
+      <Configuration>Debug</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Release|x64">
+      <Configuration>Release</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+  </ItemGroup>
+  <ItemGroup>
+    <ClCompile Include="..\..\..\test\stress\main.cpp" />
+    <ClCompile Include="..\..\..\test\stress\map\minmax\map_minmax.cpp" />
+    <ClCompile Include="..\..\..\test\stress\map\minmax\map_minmax_bronsonavltree.cpp" />
+    <ClCompile Include="..\..\..\test\stress\map\minmax\map_minmax_ellentree.cpp" />
+    <ClCompile Include="..\..\..\test\stress\map\minmax\map_minmax_skip.cpp" />
+  </ItemGroup>
+  <ItemGroup>
+    <Text Include="..\..\..\test\stress\map\minmax\CMakeLists.txt" />
+  </ItemGroup>
+  <ItemGroup>
+    <ClInclude Include="..\..\..\test\stress\map\minmax\map_minmax.h" />
+  </ItemGroup>
+  <PropertyGroup Label="Globals">
+    <ProjectGuid>{A0BC5155-F91B-4F89-B775-BB09A54EDB73}</ProjectGuid>
+    <Keyword>Win32Proj</Keyword>
+    <RootNamespace>stress_map_minmax</RootNamespace>
+    <WindowsTargetPlatformVersion>8.1</WindowsTargetPlatformVersion>
+    <ProjectName>stress-map-minmax</ProjectName>
+  </PropertyGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>false</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <WholeProgramOptimization>true</WholeProgramOptimization>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>false</UseDebugLibraries>
+    <PlatformToolset>v140</PlatformToolset>
+    <WholeProgramOptimization>true</WholeProgramOptimization>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
+  <ImportGroup Label="ExtensionSettings">
+  </ImportGroup>
+  <ImportGroup Label="Shared">
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'" Label="PropertySheets">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'" Label="PropertySheets">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets" Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+  </ImportGroup>
+  <PropertyGroup Label="UserMacros" />
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'">
+    <LinkIncremental>true</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+    <TargetName>$(ProjectName)_d</TargetName>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <LinkIncremental>false</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <LinkIncremental>false</LinkIncremental>
+    <OutDir>$(SolutionDir)..\..\..\bin\vc.$(PlatformToolset)\$(Platform)-release\</OutDir>
+    <IntDir>$(SolutionDir)..\..\..\obj\vc.$(PlatformToolset)\$(Platform)\$(ProjectName)\$(Configuration)\</IntDir>
+  </PropertyGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\map;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+      <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>DebugFastLink</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|Win32'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\map;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+      <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>DebugFastLink</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\map;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+      <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>DebugFastLink</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='DebugVLD|x64'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\map;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+      <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation>DebugFastLink</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtestd.lib;stress-framework_d.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <ClCompile>
+      <WarningLevel>Level3</WarningLevel>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <Optimization>MaxSpeed</Optimization>
+      <FunctionLevelLinking>true</FunctionLevelLinking>
+      <IntrinsicFunctions>true</IntrinsicFunctions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;WIN32;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\map;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+      <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <EnableCOMDATFolding>true</EnableCOMDATFolding>
+      <OptimizeReferences>true</OptimizeReferences>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB32);$(GTEST_ROOT)/lib/x86;$(BOOST_PATH)/stage32/lib;$(BOOST_PATH)/stage/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtest.lib;stress-framework.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <ClCompile>
+      <WarningLevel>Level3</WarningLevel>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <Optimization>MaxSpeed</Optimization>
+      <FunctionLevelLinking>true</FunctionLevelLinking>
+      <IntrinsicFunctions>true</IntrinsicFunctions>
+      <PreprocessorDefinitions>_ENABLE_ATOMIC_ALIGNMENT_FIX;CDSUNIT_USE_URCU;CDS_ENABLE_HPSTAT;NDEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <AdditionalIncludeDirectories>$(SolutionDir)..\..\..;$(GTEST_ROOT)/include;$(SolutionDir)..\..\..\test\include;$(SolutionDir)..\..\..\test\stress\map;$(SolutionDir)..\..\..\test\stress\;$(BOOST_PATH);%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories>
+      <AdditionalOptions>/bigobj %(AdditionalOptions)</AdditionalOptions>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <EnableCOMDATFolding>true</EnableCOMDATFolding>
+      <OptimizeReferences>true</OptimizeReferences>
+      <GenerateDebugInformation>true</GenerateDebugInformation>
+      <AdditionalLibraryDirectories>$(GTEST_LIB64);$(GTEST_ROOT)/lib/x64;$(BOOST_PATH)/stage64/lib;$(BOOST_PATH)/bin;%(AdditionalLibraryDirectories);$(OutDir)</AdditionalLibraryDirectories>
+      <AdditionalDependencies>gtest.lib;stress-framework.lib;%(AdditionalDependencies)</AdditionalDependencies>
+    </Link>
+  </ItemDefinitionGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
+  <ImportGroup Label="ExtensionTargets">
+  </ImportGroup>
+</Project>
\ No newline at end of file
index 59d2d05..cf18f27 100644 (file)
@@ -221,6 +221,16 @@ CuckooProbesetThreshold=0
 FeldmanMapHeadBits=8\r
 FeldmanMapArrayBits=8\r
 \r
+[map_minmax]\r
+MapSize=50000\r
+InsThreadCount=2\r
+ExtractThreadCount=2\r
+PassCount=500\r
+\r
+# *** FeldmanHashMap properties\r
+FeldmanMapHeadBits=8\r
+FeldmanMapArrayBits=8\r
+\r
 [free_list]\r
 ThreadCount=4\r
 PassCount=100000
\ No newline at end of file
index 6b45993..93d518f 100644 (file)
@@ -220,6 +220,16 @@ CuckooProbesetThreshold=0
 FeldmanMapHeadBits=8
 FeldmanMapArrayBits=8
 
+[map_minmax]
+MapSize=50000
+InsThreadCount=2
+ExtractThreadCount=2
+PassCount=500
+
+# *** FeldmanHashMap properties
+FeldmanMapHeadBits=8
+FeldmanMapArrayBits=8
+
 [free_list]
 ThreadCount=4
 PassCount=1000000
index c363038..048ab04 100644 (file)
@@ -219,6 +219,16 @@ CuckooProbesetThreshold=0
 FeldmanMapHeadBits=8\r
 FeldmanMapArrayBits=8\r
 \r
+[map_minmax]\r
+MapSize=50000\r
+InsThreadCount=2\r
+ExtractThreadCount=2\r
+PassCount=1000\r
+\r
+# *** FeldmanHashMap properties\r
+FeldmanMapHeadBits=8\r
+FeldmanMapArrayBits=8\r
+\r
 [free_list]\r
 ThreadCount=4\r
 PassCount=1000000
\ No newline at end of file
index 44e520f..c42ae7b 100644 (file)
@@ -220,6 +220,16 @@ CuckooProbesetThreshold=0
 FeldmanMapHeadBits=8\r
 FeldmanMapArrayBits=8\r
 \r
+[map_minmax]\r
+MapSize=50000\r
+InsThreadCount=4\r
+ExtractThreadCount=4\r
+PassCount=1000\r
+\r
+# *** FeldmanHashMap properties\r
+FeldmanMapHeadBits=8\r
+FeldmanMapArrayBits=8\r
+\r
 [free_list]\r
 ThreadCount=4\r
 PassCount=1000000
\ No newline at end of file
index e5d8ba8..3103c1f 100644 (file)
@@ -8,6 +8,7 @@ add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_func)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_string)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdel_item_int)
 add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/insdelfind)
+add_subdirectory(${CMAKE_CURRENT_SOURCE_DIR}/minmax)
 
 add_custom_target( stress-map
     DEPENDS
@@ -18,4 +19,5 @@ add_custom_target( stress-map
         stress-map-insdel-string
         stress-map-insdel-item-int
         stress-map-insdelfind
+        stress-map-minmax
 )
index 58a55b4..313ef2f 100644 (file)
@@ -48,10 +48,28 @@ namespace map {
         typedef cc::BronsonAVLTreeMap< GC, Key, T, Traits > base_class;
     public:
         template <typename Config>
-        BronsonAVLTreeMap( Config const& /*cfg*/)
+        BronsonAVLTreeMap( Config const& /*cfg*/ )
             : base_class()
         {}
 
+        std::pair<Key, bool> extract_min_key()
+        {
+            Key key;
+            typename base_class::exempt_ptr xp = base_class::extract_min( [&key]( Key const& k ) { key = k; } );
+            if ( xp )
+                return std::make_pair( key, true );
+            return std::make_pair( key, false );
+        }
+
+        std::pair<Key, bool> extract_max_key()
+        {
+            Key key;
+            typename base_class::exempt_ptr xp = base_class::extract_max( [&key]( Key const& k ) { key = k; } );
+            if ( xp )
+                return std::make_pair( key, true );
+            return std::make_pair( key, false );
+        }
+
         // for testing
         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
index a6ae955..d314ab2 100644 (file)
@@ -52,6 +52,22 @@ namespace map {
             : base_class()
         {}
 
+        std::pair<Key, bool> extract_min_key()
+        {
+            auto xp = base_class::extract_min();
+            if ( xp )
+                return std::make_pair( xp->first, true );
+            return std::make_pair( Key(), false );
+        }
+
+        std::pair<Key, bool> extract_max_key()
+        {
+            auto xp = base_class::extract_max();
+            if ( xp )
+                return std::make_pair( xp->first, true );
+            return std::make_pair( Key(), false );
+        }
+
         // for testing
         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
index bb744fe..9fed081 100644 (file)
@@ -52,6 +52,22 @@ namespace map {
             : base_class()
         {}
 
+        std::pair<Key, bool> extract_min_key()
+        {
+            auto xp = base_class::extract_min();
+            if ( xp )
+                return std::make_pair( xp->first, true );
+            return std::make_pair( Key(), false );
+        }
+
+        std::pair<Key, bool> extract_max_key()
+        {
+            auto xp = base_class::extract_max();
+            if ( xp )
+                return std::make_pair( xp->first, true );
+            return std::make_pair( Key(), false );
+        }
+
         // for testing
         static CDS_CONSTEXPR bool const c_bExtractSupported = true;
         static CDS_CONSTEXPR bool const c_bLoadFactorDepended = false;
diff --git a/test/stress/map/minmax/CMakeLists.txt b/test/stress/map/minmax/CMakeLists.txt
new file mode 100644 (file)
index 0000000..adaf203
--- /dev/null
@@ -0,0 +1,25 @@
+set(PACKAGE_NAME stress-map-minmax)
+
+set(CDSSTRESS_MAP_MINMAX_SOURCES
+    ../../main.cpp
+    map_minmax.cpp
+    map_minmax_bronsonavltree.cpp
+    map_minmax_ellentree.cpp
+    map_minmax_skip.cpp
+)
+
+include_directories(
+    ${CMAKE_CURRENT_SOURCE_DIR}
+    ${CMAKE_CURRENT_SOURCE_DIR}/..
+)
+
+add_executable(${PACKAGE_NAME} ${CDSSTRESS_MAP_MINMAX_SOURCES} $<TARGET_OBJECTS:${CDSSTRESS_FRAMEWORK_LIBRARY}>)
+target_link_libraries(${PACKAGE_NAME} 
+    ${CDS_SHARED_LIBRARY}
+    ${GTEST_LIBRARY}
+    ${Boost_THREAD_LIBRARY}
+    ${Boost_SYSTEM_LIBRARY}
+    ${CMAKE_THREAD_LIBS_INIT}
+)
+
+add_test(NAME ${PACKAGE_NAME} COMMAND ${PACKAGE_NAME} WORKING_DIRECTORY ${EXECUTABLE_OUTPUT_PATH})
\ No newline at end of file
diff --git a/test/stress/map/minmax/map_minmax.cpp b/test/stress/map/minmax/map_minmax.cpp
new file mode 100644 (file)
index 0000000..1d2a7fc
--- /dev/null
@@ -0,0 +1,72 @@
+/*
+    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 "map_minmax.h"
+
+namespace map {
+
+    size_t  Map_MinMax::s_nMapSize = 50000;
+    size_t  Map_MinMax::s_nInsThreadCount = 4;
+    size_t  Map_MinMax::s_nExtractThreadCount = 4;
+    size_t  Map_MinMax::s_nPassCount = 1000;
+
+    //size_t Map_MinMax::s_nFeldmanMap_HeadBits = 8;
+    //size_t Map_MinMax::s_nFeldmanMap_ArrayBits = 8;
+
+    void Map_MinMax::SetUpTestCase()
+    {
+        cds_test::config const& cfg = get_config( "map_minmax" );
+
+        s_nMapSize = cfg.get_size_t( "MapSize", s_nMapSize );
+        if ( s_nMapSize < 1000 )
+            s_nMapSize = 1000;
+
+        s_nInsThreadCount = cfg.get_size_t( "InsThreadCount", s_nInsThreadCount );
+        if ( s_nInsThreadCount == 0 )
+            s_nInsThreadCount = 1;
+
+        s_nExtractThreadCount = cfg.get_size_t( "ExtractThreadCount", s_nExtractThreadCount );
+        if ( s_nExtractThreadCount )
+            s_nExtractThreadCount = 1;
+
+        s_nPassCount = cfg.get_size_t( "PassCount", s_nPassCount );
+        if ( s_nPassCount == 0 )
+            s_nPassCount = 100;
+
+        //s_nFeldmanMap_HeadBits = cfg.get_size_t( "FeldmanMapHeadBits", s_nFeldmanMap_HeadBits );
+        //if ( s_nFeldmanMap_HeadBits == 0 )
+        //    s_nFeldmanMap_HeadBits = 4;
+
+        //s_nFeldmanMap_ArrayBits = cfg.get_size_t( "FeldmanMapArrayBits", s_nFeldmanMap_ArrayBits );
+        //if ( s_nFeldmanMap_ArrayBits == 0 )
+        //    s_nFeldmanMap_ArrayBits = 4;
+    }
+
+} // namespace map
diff --git a/test/stress/map/minmax/map_minmax.h b/test/stress/map/minmax/map_minmax.h
new file mode 100644 (file)
index 0000000..2703a05
--- /dev/null
@@ -0,0 +1,386 @@
+/*
+    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 "map_type.h"
+#include <cds/os/topology.h>
+
+namespace map {
+
+    class Map_MinMax: public cds_test::stress_fixture
+    {
+    public:
+        static size_t s_nInsThreadCount;      // insert thread count
+        static size_t s_nExtractThreadCount;  // extract thread count
+        static size_t s_nMapSize;             // max map size
+        static size_t s_nPassCount;
+
+        //static size_t s_nFeldmanMap_HeadBits;
+        //static size_t s_nFeldmanMap_ArrayBits;
+
+        static size_t  s_nLoadFactor;  // current load factor
+
+        static void SetUpTestCase();
+        //static void TearDownTestCase();
+
+    protected:
+        typedef int     key_type;
+        typedef int     value_type;
+        typedef std::pair<key_type const, value_type> pair_type;
+
+        atomics::atomic<size_t> m_nInsThreadCount;
+        key_type    m_KeyMin;
+        key_type    m_KeyMax;
+
+        enum {
+            inserter_thread,
+            extractor_thread,
+        };
+
+        template <class Map>
+        class Inserter: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Map&     m_Map;
+            std::vector<key_type> m_arr;
+
+            void init_data()
+            {
+                Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
+                key_type keyMin = fixture.m_KeyMin;
+                key_type keyMax = fixture.m_KeyMax;
+
+                for ( key_type i = keyMin + 10; i >= keyMin; --i )
+                    m_arr.push_back( i );
+                for ( key_type i = keyMax - 10; i <= keyMax; ++i )
+                    m_arr.push_back( i );
+                shuffle( m_arr.begin(), m_arr.end() );
+            }
+
+        public:
+            size_t m_nInsertMinSuccess = 0;
+            size_t m_nInsertMinFailed = 0;
+            size_t m_nInsertMaxSuccess = 0;
+            size_t m_nInsertMaxFailed = 0;
+
+        public:
+            Inserter( cds_test::thread_pool& pool, Map& map )
+                : base_class( pool, inserter_thread )
+                , m_Map( map )
+            {
+                init_data();
+            }
+
+            Inserter( Inserter& src )
+                : base_class( src )
+                , m_Map( src.m_Map )
+            {
+                init_data();
+            }
+
+            virtual thread * clone()
+            {
+                return new Inserter( *this );
+            }
+
+            virtual void test()
+            {
+                Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
+
+                key_type keyMin = fixture.m_KeyMin;
+                key_type keyMax = fixture.m_KeyMax;
+
+                for ( size_t nPass = 0; nPass < s_nPassCount; ++nPass ) {
+                    for ( key_type key : m_arr ) {
+                        if ( m_Map.insert( key, key ) ) {
+                            if ( key == keyMin )
+                                ++m_nInsertMinSuccess;
+                            else if ( key == keyMax )
+                                ++m_nInsertMaxSuccess;
+                        }
+                        else {
+                            if ( key == keyMin )
+                                ++m_nInsertMinFailed;
+                            else if ( key == keyMax )
+                                ++m_nInsertMaxFailed;
+                        }
+                    }
+                }
+
+                fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
+            }
+        };
+
+        // Deletes odd keys from [0..N)
+        template <class GC, class Map >
+        class Extractor: public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Map&     m_Map;
+
+        public:
+            size_t  m_nDeleteMin = 0;
+            size_t  m_nDeleteMinFailed = 0;
+            size_t  m_nDeleteMax = 0;
+            size_t  m_nDeleteMaxFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Map& map )
+                : base_class( pool, extractor_thread )
+                , m_Map( map )
+            {}
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Map( src.m_Map )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Map& rMap = m_Map;
+
+                typename Map::guarded_ptr gp;
+                Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
+
+                key_type keyMin = fixture.m_KeyMin;
+                key_type keyMax = fixture.m_KeyMax;
+
+                do {
+                    gp = rMap.extract_min();
+                    if ( gp ) {
+                        if ( gp->first == keyMin )
+                            ++m_nDeleteMin;
+                    }
+                    else
+                        ++m_nDeleteMinFailed;
+
+                    gp = rMap.extract_max();
+                    if ( gp ) {
+                        if ( gp->first == keyMax )
+                            ++m_nDeleteMax;
+                    }
+                    else
+                        ++m_nDeleteMaxFailed;
+
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+            }
+        };
+
+        template <class RCU, class Map >
+        class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
+        {
+            typedef cds_test::thread base_class;
+            Map&     m_Map;
+
+        public:
+            size_t  m_nDeleteMin = 0;
+            size_t  m_nDeleteMinFailed = 0;
+            size_t  m_nDeleteMax = 0;
+            size_t  m_nDeleteMaxFailed = 0;
+
+        public:
+            Extractor( cds_test::thread_pool& pool, Map& map )
+                : base_class( pool, extractor_thread )
+                , m_Map( map )
+            {}
+
+            Extractor( Extractor& src )
+                : base_class( src )
+                , m_Map( src.m_Map )
+            {}
+
+            virtual thread * clone()
+            {
+                return new Extractor( *this );
+            }
+
+            virtual void test()
+            {
+                Map& rMap = m_Map;
+                Map_MinMax& fixture = pool().template fixture<Map_MinMax>();
+
+                key_type keyMin = fixture.m_KeyMin;
+                key_type keyMax = fixture.m_KeyMax;
+
+                static_assert( !Map::c_bExtractLockExternal, "No external RCU locking required" );
+
+                do {
+                    auto res = rMap.extract_min_key();
+                    if ( res.second ) {
+                        if ( res.first == keyMin )
+                            ++m_nDeleteMin;
+                    }
+                    else
+                        ++m_nDeleteMinFailed;
+
+                    res = rMap.extract_max_key();
+                    if ( res.second ) {
+                        if ( res.first == keyMax )
+                            ++m_nDeleteMax;
+                    }
+                    else
+                        ++m_nDeleteMaxFailed;
+                } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
+
+                auto res = rMap.extract_min_key();
+                if ( res.second ) {
+                    if ( res.first == keyMin )
+                        ++m_nDeleteMin;
+                }
+                else
+                    ++m_nDeleteMinFailed;
+
+                res = rMap.extract_max_key();
+                if ( res.second ) {
+                    if ( res.first == keyMax )
+                        ++m_nDeleteMax;
+                }
+                else
+                    ++m_nDeleteMaxFailed;
+            }
+        };
+
+    protected:
+        template <class Map>
+        void do_test( Map& testMap )
+        {
+            typedef Inserter<Map> insert_thread;
+            typedef Extractor< typename Map::gc, Map > extract_thread;
+
+            m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
+
+            {
+                std::vector<key_type> arr;
+                arr.resize( s_nMapSize );
+                for ( int i = 0; i < static_cast<int>( s_nMapSize ); ++i )
+                    arr[i] = i;;
+                shuffle( arr.begin(), arr.end() );
+
+                for ( key_type key : arr )
+                    testMap.insert( key, key );
+            }
+
+            m_KeyMin = 0;
+            m_KeyMax = static_cast<int>( s_nMapSize - 1 );
+
+            cds_test::thread_pool& pool = get_pool();
+            pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
+            pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
+
+            propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
+                << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
+                << std::make_pair( "map_size", s_nMapSize )
+                << std::make_pair( "pass_count", s_nPassCount );
+
+            std::chrono::milliseconds duration = pool.run();
+
+            propout() << std::make_pair( "duration", duration );
+
+            size_t nInsertMinSuccess = 0;
+            size_t nInsertMinFailed = 0;
+            size_t nInsertMaxSuccess = 0;
+            size_t nInsertMaxFailed = 0;
+            size_t nDeleteMin = 0;
+            size_t nDeleteMinFailed = 0;
+            size_t nDeleteMax = 0;
+            size_t nDeleteMaxFailed = 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);
+                    nInsertMinSuccess += inserter.m_nInsertMinSuccess;
+                    nInsertMinFailed += inserter.m_nInsertMinFailed;
+                    nInsertMaxSuccess += inserter.m_nInsertMaxSuccess;
+                    nInsertMaxFailed += inserter.m_nInsertMaxFailed;
+                }
+                break;
+                case extractor_thread:
+                {
+                    extract_thread& extractor = static_cast<extract_thread&>(thr);
+                    nDeleteMin += extractor.m_nDeleteMin;
+                    nDeleteMinFailed += extractor.m_nDeleteMinFailed;
+                    nDeleteMax += extractor.m_nDeleteMax;
+                    nDeleteMaxFailed += extractor.m_nDeleteMaxFailed;
+                }
+                break;
+                default:
+                    assert( false );
+                }
+            }
+
+            EXPECT_EQ( nDeleteMinFailed, 0u );
+            EXPECT_EQ( nDeleteMaxFailed, 0u );
+
+            EXPECT_EQ( nDeleteMin, nInsertMinSuccess + 1 );
+            EXPECT_EQ( nDeleteMax, nInsertMaxSuccess + 1 );
+
+            propout()
+                << std::make_pair( "insert_min", nInsertMinSuccess + 1 )
+                << std::make_pair( "insert_min_double", nInsertMinFailed )
+                << std::make_pair( "insert_max", nInsertMaxSuccess + 1 )
+                << std::make_pair( "insert_max_double", nInsertMaxFailed )
+                << std::make_pair( "extract_min", nDeleteMin )
+                << std::make_pair( "extract_min_failed", nDeleteMinFailed )
+                << std::make_pair( "extract_max", nDeleteMax )
+                << std::make_pair( "extract_max_failed", nDeleteMaxFailed );
+
+            analyze( testMap );
+        }
+
+        template <class Map>
+        void analyze( Map& testMap )
+        {
+            print_stat( propout(), testMap );
+
+            check_before_cleanup( testMap );
+            testMap.clear();
+            EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
+
+            additional_check( testMap );
+            additional_cleanup( testMap );
+        }
+
+        template <class Map>
+        void run_test()
+        {
+            static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
+            Map testMap( *this );
+            do_test( testMap );
+        }
+    };
+
+} // namespace map
diff --git a/test/stress/map/minmax/map_minmax_bronsonavltree.cpp b/test/stress/map/minmax/map_minmax_bronsonavltree.cpp
new file mode 100644 (file)
index 0000000..3319a0b
--- /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 "map_minmax.h"
+#include "map_type_bronson_avltree.h"
+
+namespace map {
+
+    CDSSTRESS_BronsonAVLTreeMap( Map_MinMax, run_test, int, int )
+
+} // namespace map
diff --git a/test/stress/map/minmax/map_minmax_ellentree.cpp b/test/stress/map/minmax/map_minmax_ellentree.cpp
new file mode 100644 (file)
index 0000000..3329efa
--- /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 "map_minmax.h"
+#include "map_type_ellen_bintree.h"
+
+namespace map {
+
+    CDSSTRESS_EllenBinTreeMap( Map_MinMax, run_test, int, int )
+
+} // namespace map
diff --git a/test/stress/map/minmax/map_minmax_skip.cpp b/test/stress/map/minmax/map_minmax_skip.cpp
new file mode 100644 (file)
index 0000000..c75767a
--- /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 "map_minmax.h"
+#include "map_type_skip_list.h"
+
+namespace map {
+
+    CDSSTRESS_SkipListMap( Map_MinMax, run_test, int, int )
+
+} // namespace map