50 changes: 25 additions & 25 deletions include/boost/move/detail/move_helpers.hpp
View file
Expand Up @@ -69,26 +69,26 @@
{};

#define BOOST_MOVE_CONVERSION_AWARE_CATCH_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\
RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_CONST(TYPE) x)\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_CONST(TYPE) x)\
{ return FWD_FUNCTION(static_cast<const TYPE&>(x)); }\
\
RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
{ return FWD_FUNCTION(::boost::move(x)); }\
\
RETURN_VALUE PUB_FUNCTION(TYPE &x)\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(TYPE &x)\
{ return FWD_FUNCTION(const_cast<const TYPE &>(x)); }\
//
#if defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
#define BOOST_MOVE_CONVERSION_AWARE_CATCH(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\
BOOST_MOVE_CONVERSION_AWARE_CATCH_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
RETURN_VALUE PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u,\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u,\
typename boost_move_conversion_aware_catch_1< ::boost::move_detail::nat, BOOST_MOVE_TEMPL_PARAM, TYPE>::type* = 0)\
{ return FWD_FUNCTION(u); }\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
RETURN_VALUE PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u,\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u,\
typename boost_move_conversion_aware_catch_2< ::boost::move_detail::nat, BOOST_MOVE_TEMPL_PARAM, TYPE>::type* = 0)\
{\
TYPE t((u));\
Expand All @@ -100,12 +100,12 @@
BOOST_MOVE_CONVERSION_AWARE_CATCH_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
typename boost_move_conversion_aware_catch_1<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, TYPE>::type\
BOOST_MOVE_FORCEINLINE typename boost_move_conversion_aware_catch_1<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, TYPE>::type\
PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u)\
{ return FWD_FUNCTION(u); }\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
typename boost_move_conversion_aware_catch_2<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, TYPE>::type\
BOOST_MOVE_FORCEINLINE typename boost_move_conversion_aware_catch_2<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, TYPE>::type\
PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u)\
{\
TYPE t((u));\
Expand All @@ -116,14 +116,14 @@
#elif (defined(_MSC_VER) && (_MSC_VER == 1600))

#define BOOST_MOVE_CONVERSION_AWARE_CATCH(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\
RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_CONST(TYPE) x)\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_CONST(TYPE) x)\
{ return FWD_FUNCTION(static_cast<const TYPE&>(x)); }\
\
RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
{ return FWD_FUNCTION(::boost::move(x)); }\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
typename ::boost::move_detail::enable_if_c\
BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::enable_if_c\
< !::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM>::value\
, RETURN_VALUE >::type\
PUB_FUNCTION(const BOOST_MOVE_TEMPL_PARAM &u)\
Expand All @@ -136,10 +136,10 @@
#else //BOOST_NO_CXX11_RVALUE_REFERENCES

#define BOOST_MOVE_CONVERSION_AWARE_CATCH(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION)\
RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_CONST(TYPE) x)\
{ return FWD_FUNCTION(static_cast<const TYPE&>(x)); }\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_CONST(TYPE) x)\
{ return FWD_FUNCTION(x); }\
\
RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
{ return FWD_FUNCTION(::boost::move(x)); }\
//

Expand Down Expand Up @@ -174,26 +174,26 @@
{};

#define BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_CONST(TYPE) x)\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_CONST(TYPE) x)\
{ return FWD_FUNCTION(arg1, static_cast<const TYPE&>(x)); }\
\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
{ return FWD_FUNCTION(arg1, ::boost::move(x)); }\
\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, TYPE &x)\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, TYPE &x)\
{ return FWD_FUNCTION(arg1, const_cast<const TYPE &>(x)); }\
//
#if defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN)
#define BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\
BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u,\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u,\
typename boost_move_conversion_aware_catch_1arg_1<void, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type* = 0)\
{ return FWD_FUNCTION(arg1, u); }\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u,\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u,\
typename boost_move_conversion_aware_catch_1arg_2<void, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type* = 0)\
{\
TYPE t((u));\
Expand All @@ -205,12 +205,12 @@
BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG_COMMON(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
typename boost_move_conversion_aware_catch_1arg_1<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type\
BOOST_MOVE_FORCEINLINE typename boost_move_conversion_aware_catch_1arg_1<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type\
PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u)\
{ return FWD_FUNCTION(arg1, u); }\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
typename boost_move_conversion_aware_catch_1arg_2<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type\
BOOST_MOVE_FORCEINLINE typename boost_move_conversion_aware_catch_1arg_2<RETURN_VALUE, BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO, TYPE>::type\
PUB_FUNCTION(ARG1 arg1, const BOOST_MOVE_TEMPL_PARAM &u)\
{\
TYPE t((u));\
Expand All @@ -222,14 +222,14 @@
#elif (defined(_MSC_VER) && (_MSC_VER == 1600))

#define BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_CONST(TYPE) x)\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_CONST(TYPE) x)\
{ return FWD_FUNCTION(arg1, static_cast<const TYPE&>(x)); }\
\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
{ return FWD_FUNCTION(arg1, ::boost::move(x)); }\
\
template<class BOOST_MOVE_TEMPL_PARAM>\
typename ::boost::move_detail::disable_if_or\
BOOST_MOVE_FORCEINLINE typename ::boost::move_detail::disable_if_or\
< RETURN_VALUE \
, ::boost::move_detail::is_same<TYPE, BOOST_MOVE_TEMPL_PARAM> \
, ::boost::move_detail::is_same_or_convertible<BOOST_MOVE_TEMPL_PARAM, UNLESS_CONVERTIBLE_TO> \
Expand All @@ -244,10 +244,10 @@
#else

#define BOOST_MOVE_CONVERSION_AWARE_CATCH_1ARG(PUB_FUNCTION, TYPE, RETURN_VALUE, FWD_FUNCTION, ARG1, UNLESS_CONVERTIBLE_TO)\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_CONST(TYPE) x)\
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_CONST(TYPE) x)\
{ return FWD_FUNCTION(arg1, static_cast<const TYPE&>(x)); }\
\
RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
BOOST_MOVE_FORCEINLINE RETURN_VALUE PUB_FUNCTION(ARG1 arg1, BOOST_MOVE_CATCH_RVALUE(TYPE) x) \
{ return FWD_FUNCTION(arg1, ::boost::move(x)); }\
//

Expand Down
5 changes: 3 additions & 2 deletions include/boost/move/detail/workaround.hpp
View file
Expand Up @@ -52,15 +52,16 @@
#define BOOST_MOVE_MSVC_AUTO_MOVE_RETURN_BUG
#endif

#define BOOST_MOVE_DISABLE_FORCEINLINE

#if defined(BOOST_MOVE_DISABLE_FORCEINLINE)
#define BOOST_MOVE_FORCEINLINE inline
#elif defined(BOOST_MOVE_FORCEINLINE_IS_BOOST_FORCELINE)
#define BOOST_MOVE_FORCEINLINE BOOST_FORCEINLINE
#elif defined(BOOST_MSVC) && defined(_DEBUG)
//"__forceinline" and MSVC seems to have some bugs in debug mode
#define BOOST_MOVE_FORCEINLINE inline
#elif defined(__GNUC__) && ((__GNUC__ < 4) || (__GNUC__ == 4 && (__GNUC_MINOR__ < 5)))
//Older GCCs have problems with forceinline
#define BOOST_MOVE_FORCEINLINE inline
#else
#define BOOST_MOVE_FORCEINLINE BOOST_FORCEINLINE
#endif
Expand Down
8 changes: 8 additions & 0 deletions proj/vc7ide/Move.sln
View file
Expand Up @@ -131,6 +131,10 @@ Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "doc_template_assign", "doc_
ProjectSection(ProjectDependencies) = postProject
EndProjectSection
EndProject
Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "inplace_merge_test", "inplace_merge_test.vcproj", "{CD617C28-62B7-CE9E-0000-000000000000}"
ProjectSection(ProjectDependencies) = postProject
EndProjectSection
EndProject
Global
GlobalSection(SolutionConfiguration) = preSolution
Debug = Debug
Expand Down Expand Up @@ -271,6 +275,10 @@ Global
{7460CA18-D532-E4F8-F1F2-3A796D2A91E2}.Debug.Build.0 = Debug|Win32
{7460CA18-D532-E4F8-F1F2-3A796D2A91E2}.Release.ActiveCfg = Release|Win32
{7460CA18-D532-E4F8-F1F2-3A796D2A91E2}.Release.Build.0 = Release|Win32
{CD617C28-62B7-CE9E-0000-000000000000}.Debug.ActiveCfg = Debug|Win32
{CD617C28-62B7-CE9E-0000-000000000000}.Debug.Build.0 = Debug|Win32
{CD617C28-62B7-CE9E-0000-000000000000}.Release.ActiveCfg = Release|Win32
{CD617C28-62B7-CE9E-0000-000000000000}.Release.Build.0 = Release|Win32
EndGlobalSection
GlobalSection(SolutionItems) = postSolution
..\..\..\..\boost\move\algo\adaptive_merge.hpp = ..\..\..\..\boost\move\algo\adaptive_merge.hpp
Expand Down
134 changes: 134 additions & 0 deletions proj/vc7ide/inplace_merge_test.vcproj
View file
@@ -0,0 +1,134 @@
<?xml version="1.0" encoding="Windows-1252"?>
<VisualStudioProject
ProjectType="Visual C++"
Version="7.10"
Name="inplace_merge_test"
ProjectGUID="{CD617C28-62B7-CE9E-0000-000000000000}"
Keyword="Win32Proj">
<Platforms>
<Platform
Name="Win32"/>
</Platforms>
<Configurations>
<Configuration
Name="Debug|Win32"
OutputDirectory="../../Bin/Win32/Debug"
IntermediateDirectory="Debug/inplace_merge_test"
ConfigurationType="1"
CharacterSet="2">
<Tool
Name="VCCLCompilerTool"
Optimization="0"
AdditionalIncludeDirectories="../../../.."
PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE;BOOST_DATE_TIME_NO_LIB"
MinimalRebuild="TRUE"
BasicRuntimeChecks="3"
RuntimeLibrary="3"
DisableLanguageExtensions="FALSE"
TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="TRUE"
UsePrecompiledHeader="0"
WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="3"/>
<Tool
Name="VCCustomBuildTool"/>
<Tool
Name="VCLinkerTool"
AdditionalDependencies="winmm.lib"
OutputFile="$(OutDir)/inplace_merge_test_d.exe"
LinkIncremental="1"
AdditionalLibraryDirectories="../../../../stage/lib"
GenerateDebugInformation="TRUE"
ProgramDatabaseFile="$(OutDir)/inplace_merge_test.pdb"
SubSystem="1"
TargetMachine="1"
FixedBaseAddress="1"/>
<Tool
Name="VCMIDLTool"/>
<Tool
Name="VCPostBuildEventTool"/>
<Tool
Name="VCPreBuildEventTool"/>
<Tool
Name="VCPreLinkEventTool"/>
<Tool
Name="VCResourceCompilerTool"/>
<Tool
Name="VCWebServiceProxyGeneratorTool"/>
<Tool
Name="VCXMLDataGeneratorTool"/>
<Tool
Name="VCWebDeploymentTool"/>
<Tool
Name="VCManagedWrapperGeneratorTool"/>
<Tool
Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
</Configuration>
<Configuration
Name="Release|Win32"
OutputDirectory="../../Bin/Win32/Release"
IntermediateDirectory="Release/inplace_merge_test"
ConfigurationType="1"
CharacterSet="2">
<Tool
Name="VCCLCompilerTool"
AdditionalIncludeDirectories="../../../.."
PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE;BOOST_DATE_TIME_NO_LIB"
RuntimeLibrary="2"
TreatWChar_tAsBuiltInType="TRUE"
ForceConformanceInForLoopScope="FALSE"
UsePrecompiledHeader="0"
WarningLevel="4"
Detect64BitPortabilityProblems="TRUE"
DebugInformationFormat="0"/>
<Tool
Name="VCCustomBuildTool"/>
<Tool
Name="VCLinkerTool"
AdditionalDependencies="winmm.lib"
OutputFile="$(OutDir)/inplace_merge_test.exe"
LinkIncremental="1"
AdditionalLibraryDirectories="../../../../stage/lib"
GenerateDebugInformation="TRUE"
SubSystem="1"
OptimizeReferences="2"
EnableCOMDATFolding="2"
TargetMachine="1"/>
<Tool
Name="VCMIDLTool"/>
<Tool
Name="VCPostBuildEventTool"/>
<Tool
Name="VCPreBuildEventTool"/>
<Tool
Name="VCPreLinkEventTool"/>
<Tool
Name="VCResourceCompilerTool"/>
<Tool
Name="VCWebServiceProxyGeneratorTool"/>
<Tool
Name="VCXMLDataGeneratorTool"/>
<Tool
Name="VCWebDeploymentTool"/>
<Tool
Name="VCManagedWrapperGeneratorTool"/>
<Tool
Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
</Configuration>
</Configurations>
<References>
</References>
<Files>
<Filter
Name="Source Files"
Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"
UniqueIdentifier="{870D8633-604305-5C-5C56-3BAD7A55FE7A}">
<File
RelativePath="..\..\test\inplace_merge_test.cpp">
</File>
</Filter>
</Files>
<Globals>
</Globals>
</VisualStudioProject>
36 changes: 14 additions & 22 deletions test/adaptive_merge_test.cpp
View file
Expand Up @@ -10,20 +10,15 @@
//////////////////////////////////////////////////////////////////////////////

#include <cstdlib> //std::srand
#include <algorithm> //std::next_permutation
#include <iostream> //std::cout

#include <boost/config.hpp>

#include <boost/move/unique_ptr.hpp>
#include <boost/container/vector.hpp>
#include <boost/timer/timer.hpp>

using boost::timer::cpu_timer;
using boost::timer::cpu_times;
using boost::timer::nanosecond_type;
#include <boost/move/algo/detail/merge_sort.hpp>

#include "order_type.hpp"
#include "random_shuffle.hpp"

#include <boost/move/algo/adaptive_merge.hpp>
#include <boost/move/core.hpp>
Expand All @@ -46,22 +41,23 @@ bool test_random_shuffled(std::size_t const element_count, std::size_t const num

for (std::size_t i = 0; i != num_iter; ++i)
{
std::random_shuffle(elements.get(), elements.get() + element_count);
::random_shuffle(elements.get(), elements.get() + element_count);
for(std::size_t i = 0; i < (num_keys ? num_keys : element_count); ++i){
key_reps[i]=0;
}
for(std::size_t i = 0; i < element_count; ++i){
elements[i].val = key_reps[elements[i].key]++;
}

boost::container::vector<order_type> tmp(elements.get(), elements.get()+element_count);
boost::movelib::unique_ptr<char[]> buf(new char [sizeof(T)*(element_count-element_count/2)]);

std::size_t const split = std::size_t(std::rand()) % element_count;
std::stable_sort(tmp.data(), tmp.data()+split, order_type_less<order_type>());
std::stable_sort(tmp.data()+split, tmp.data()+element_count, order_type_less<order_type>());
boost::movelib::merge_sort(elements.get(), elements.get()+split, order_type_less(), (T*)buf.get());
boost::movelib::merge_sort(elements.get()+split, elements.get()+element_count, order_type_less(), (T*)buf.get());

boost::movelib::adaptive_merge(tmp.data(), tmp.data()+split, tmp.data()+element_count, order_type_less<order_type>());
boost::movelib::adaptive_merge(elements.get(), elements.get()+split, elements.get()+element_count, order_type_less());

if (!is_order_type_ordered(tmp.data(), element_count))
if (!is_order_type_ordered(elements.get(), element_count))
{
std::cout << "\n ERROR\n";
throw int(0);
Expand All @@ -72,16 +68,12 @@ bool test_random_shuffled(std::size_t const element_count, std::size_t const num

int main()
{
#ifdef NDEBUG
const std::size_t NIter = 100;
#else
const std::size_t NIter = 10;
#endif
test_random_shuffled<order_type>(10001, 65, NIter);
test_random_shuffled<order_type>(10001, 101, NIter);
test_random_shuffled<order_type>(10001, 1023, NIter);
test_random_shuffled<order_type>(10001, 4095, NIter);
test_random_shuffled<order_type>(10001, 0, NIter);
test_random_shuffled<order_move_type>(10001, 65, NIter);
test_random_shuffled<order_move_type>(10001, 101, NIter);
test_random_shuffled<order_move_type>(10001, 1023, NIter);
test_random_shuffled<order_move_type>(10001, 4095, NIter);
test_random_shuffled<order_move_type>(10001, 0, NIter);

return 0;
}
28 changes: 9 additions & 19 deletions test/adaptive_sort_test.cpp
View file
Expand Up @@ -10,7 +10,6 @@
//////////////////////////////////////////////////////////////////////////////

#include <cstdlib> //std::srand
#include <algorithm> //std::next_permutation
#include <iostream> //std::cout

#include <boost/config.hpp>
Expand All @@ -19,11 +18,8 @@
#include <boost/container/vector.hpp>
#include <boost/timer/timer.hpp>

using boost::timer::cpu_timer;
using boost::timer::cpu_times;
using boost::timer::nanosecond_type;

#include "order_type.hpp"
#include "random_shuffle.hpp"

#include <boost/move/algo/adaptive_sort.hpp>
#include <boost/move/core.hpp>
Expand All @@ -45,19 +41,17 @@ bool test_random_shuffled(std::size_t const element_count, std::size_t const num

for (std::size_t i = 0; i != num_iter; ++i)
{
std::random_shuffle(elements.get(), elements.get() + element_count);
::random_shuffle(elements.get(), elements.get() + element_count);
for(std::size_t i = 0; i < (num_keys ? num_keys : element_count); ++i){
key_reps[i]=0;
}
for(std::size_t i = 0; i < element_count; ++i){
elements[i].val = key_reps[elements[i].key]++;
}

boost::container::vector<order_type> tmp(elements.get(), elements.get()+element_count);

boost::movelib::adaptive_sort(tmp.data(), tmp.data()+element_count, order_type_less<order_type>());
boost::movelib::adaptive_sort(elements.get(), elements.get()+element_count, order_type_less());

if (!is_order_type_ordered(tmp.data(), element_count))
if (!is_order_type_ordered(elements.get(), element_count))
{
std::cout << "\n ERROR\n";
throw int(0);
Expand All @@ -68,16 +62,12 @@ bool test_random_shuffled(std::size_t const element_count, std::size_t const num

int main()
{
#ifdef NDEBUG
const std::size_t NIter = 100;
#else
const std::size_t NIter = 10;
#endif
test_random_shuffled<order_type>(10001, 65, NIter);
test_random_shuffled<order_type>(10001, 101, NIter);
test_random_shuffled<order_type>(10001, 1023, NIter);
test_random_shuffled<order_type>(10001, 4095, NIter);
test_random_shuffled<order_type>(10001, 0, NIter);
test_random_shuffled<order_move_type>(10001, 65, NIter);
test_random_shuffled<order_move_type>(10001, 101, NIter);
test_random_shuffled<order_move_type>(10001, 1023, NIter);
test_random_shuffled<order_move_type>(10001, 4095, NIter);
test_random_shuffled<order_move_type>(10001, 0, NIter);

return 0;
}
93 changes: 45 additions & 48 deletions test/bench_merge.cpp
View file
Expand Up @@ -27,7 +27,7 @@ using boost::timer::nanosecond_type;
//#define BOOST_MOVE_ADAPTIVE_SORT_STATS
void print_stats(const char *str, boost::ulong_long_type element_count)
{
std::printf("%sCmp:%8.04f Cpy:%9.04f\n", str, double(order_type::num_compare)/element_count, double(order_type::num_copy)/element_count );
std::printf("%sCmp:%8.04f Cpy:%9.04f\n", str, double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
}

#include <boost/move/algo/adaptive_merge.hpp>
Expand Down Expand Up @@ -83,7 +83,7 @@ const char *AlgoNames [] = { "StdMerge "
, "SqrtHAdaptMerge "
, "SqrtAdaptMerge "
, "Sqrt2AdaptMerge "
, "QuartAdaptMerge "
, "QHalfAdaptMerge "
, "StdInplaceMerge "
};

Expand All @@ -92,53 +92,53 @@ BOOST_STATIC_ASSERT((sizeof(AlgoNames)/sizeof(*AlgoNames)) == MaxMerge);
template<class T>
bool measure_algo(T *elements, std::size_t key_reps[], std::size_t element_count, std::size_t key_len, unsigned alg, nanosecond_type &prev_clock)
{
std::size_t const split_pos = generate_elements(elements, element_count, key_reps, key_len, order_type_less<T>());
std::size_t const split_pos = generate_elements(elements, element_count, key_reps, key_len, order_type_less());

std::printf("%s ", AlgoNames[alg]);
order_type::num_compare=0;
order_type::num_copy=0;
order_type::num_elements = element_count;
order_perf_type::num_compare=0;
order_perf_type::num_copy=0;
order_perf_type::num_elements = element_count;
cpu_timer timer;
timer.resume();
switch(alg)
{
case StdMerge:
std::inplace_merge(elements, elements+split_pos, elements+element_count, order_type_less<T>());
std::inplace_merge(elements, elements+split_pos, elements+element_count, order_type_less());
break;
case AdaptiveMerge:
boost::movelib::adaptive_merge(elements, elements+split_pos, elements+element_count, order_type_less<T>());
boost::movelib::adaptive_merge(elements, elements+split_pos, elements+element_count, order_type_less());
break;
case SqrtHAdaptiveMerge:
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less<T>()
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
break;
case SqrtAdaptiveMerge:
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less<T>()
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
break;
case Sqrt2AdaptiveMerge:
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less<T>()
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
, 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
break;
case QuartAdaptiveMerge:
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less<T>()
adaptive_merge_buffered( elements, elements+split_pos, elements+element_count, order_type_less()
, (element_count-1)/4+1);
break;
case StdInplaceMerge:
boost::movelib::merge_bufferless_ONlogN(elements, elements+split_pos, elements+element_count, order_type_less<T>());
boost::movelib::merge_bufferless_ONlogN(elements, elements+split_pos, elements+element_count, order_type_less());
break;
}
timer.stop();

if(order_type::num_elements == element_count){
if(order_perf_type::num_elements == element_count){
std::printf(" Tmp Ok ");
} else{
std::printf(" Tmp KO ");
}
nanosecond_type new_clock = timer.elapsed().wall;

//std::cout << "Cmp:" << order_type::num_compare << " Cpy:" << order_type::num_copy; //for old compilers without ll size argument
std::printf("Cmp:%8.04f Cpy:%9.04f", double(order_type::num_compare)/element_count, double(order_type::num_copy)/element_count );
//std::cout << "Cmp:" << order_perf_type::num_compare << " Cpy:" << order_perf_type::num_copy; //for old compilers without ll size argument
std::printf("Cmp:%8.04f Cpy:%9.04f", double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );

double time = double(new_clock);

Expand Down Expand Up @@ -178,10 +178,10 @@ bool measure_all(std::size_t L, std::size_t NK)
nanosecond_type back_clock;
bool res = true;
res = res && measure_algo(A,Keys,L,NK,StdMerge, prev_clock);
back_clock = prev_clock;/*
back_clock = prev_clock;
//
prev_clock = back_clock;
res = res && measure_algo(A,Keys,L,NK,QuartAdaptiveMerge, prev_clock);*/
res = res && measure_algo(A,Keys,L,NK,QuartAdaptiveMerge, prev_clock);
//
prev_clock = back_clock;
res = res && measure_algo(A,Keys,L,NK,Sqrt2AdaptiveMerge, prev_clock);
Expand Down Expand Up @@ -211,58 +211,55 @@ int main()
{
try{
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(101,1);
measure_all<order_type>(101,7);
measure_all<order_type>(101,31);
measure_all<order_perf_type>(101,1);
measure_all<order_perf_type>(101,7);
measure_all<order_perf_type>(101,31);
#endif
measure_all<order_type>(101,0);
measure_all<order_perf_type>(101,0);

//
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(1101,1);
measure_all<order_type>(1001,7);
measure_all<order_type>(1001,31);
measure_all<order_type>(1001,127);
measure_all<order_type>(1001,511);
measure_all<order_perf_type>(1101,1);
measure_all<order_perf_type>(1001,7);
measure_all<order_perf_type>(1001,31);
measure_all<order_perf_type>(1001,127);
measure_all<order_perf_type>(1001,511);
#endif
measure_all<order_type>(1001,0);
measure_all<order_perf_type>(1001,0);
//
#ifndef BENCH_MERGE_SHORT
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(10001,65);
measure_all<order_type>(10001,255);
measure_all<order_type>(10001,1023);
measure_all<order_type>(10001,4095);
measure_all<order_perf_type>(10001,65);
measure_all<order_perf_type>(10001,255);
measure_all<order_perf_type>(10001,1023);
measure_all<order_perf_type>(10001,4095);
#endif
measure_all<order_type>(10001,0);
measure_all<order_perf_type>(10001,0);

//
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(100001,511);
measure_all<order_type>(100001,2047);
measure_all<order_type>(100001,8191);
measure_all<order_type>(100001,32767);
measure_all<order_perf_type>(100001,511);
measure_all<order_perf_type>(100001,2047);
measure_all<order_perf_type>(100001,8191);
measure_all<order_perf_type>(100001,32767);
#endif
measure_all<order_type>(100001,0);
measure_all<order_perf_type>(100001,0);

//
#ifdef NDEBUG
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(1000001,1);
measure_all<order_type>(1000001,1024);
measure_all<order_type>(1000001,32768);
measure_all<order_type>(1000001,524287);
measure_all<order_perf_type>(1000001,1);
measure_all<order_perf_type>(1000001,1024);
measure_all<order_perf_type>(1000001,32768);
measure_all<order_perf_type>(1000001,524287);
#endif
measure_all<order_type>(1000001,0);
measure_all<order_type>(1500001,0);
//measure_all<order_type>(10000001,0);
//measure_all<order_type>(15000001,0);
//measure_all<order_type>(100000001,0);
measure_all<order_perf_type>(1000001,0);
measure_all<order_perf_type>(3000001,0);
#endif //NDEBUG

#endif //#ifndef BENCH_MERGE_SHORT

//measure_all<order_type>(100000001,0);
//measure_all<order_perf_type>(100000001,0);
}
catch(...)
{
Expand Down
107 changes: 49 additions & 58 deletions test/bench_sort.cpp
View file
Expand Up @@ -26,15 +26,15 @@ using boost::timer::nanosecond_type;
#include "order_type.hpp"

//#define BOOST_MOVE_ADAPTIVE_SORT_STATS
//#define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
void print_stats(const char *str, boost::ulong_long_type element_count)
{
std::printf("%sCmp:%7.03f Cpy:%8.03f\n", str, double(order_type::num_compare)/element_count, double(order_type::num_copy)/element_count );
std::printf("%sCmp:%7.03f Cpy:%8.03f\n", str, double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
}


#include <boost/move/algo/adaptive_sort.hpp>
#include <boost/move/algo/detail/merge_sort.hpp>
#include <boost/move/algo/detail/bufferless_merge_sort.hpp>
#include <boost/move/core.hpp>

template<class T>
Expand Down Expand Up @@ -79,7 +79,6 @@ enum AlgoType
SqrtAdaptiveSort,
Sqrt2AdaptiveSort,
QuartAdaptiveSort,
NoBufMergeSort,
InplaceStableSort,
SlowStableSort,
HeapSort,
Expand All @@ -93,7 +92,6 @@ const char *AlgoNames [] = { "MergeSort "
, "SqrtAdaptSort "
, "Sqrt2AdaptSort "
, "QuartAdaptSort "
, "NoBufMergeSort "
, "InplStableSort "
, "SlowSort "
, "HeapSort "
Expand All @@ -107,63 +105,60 @@ bool measure_algo(T *elements, std::size_t key_reps[], std::size_t element_count
generate_elements(elements, element_count, key_reps, key_len);

std::printf("%s ", AlgoNames[alg]);
order_type::num_compare=0;
order_type::num_copy=0;
order_type::num_elements = element_count;
order_perf_type::num_compare=0;
order_perf_type::num_copy=0;
order_perf_type::num_elements = element_count;
cpu_timer timer;
timer.resume();
switch(alg)
{
case MergeSort:
merge_sort_buffered(elements, element_count, order_type_less<T>());
merge_sort_buffered(elements, element_count, order_type_less());
break;
case StableSort:
std::stable_sort(elements,elements+element_count,order_type_less<T>());
std::stable_sort(elements,elements+element_count,order_type_less());
break;
case AdaptiveSort:
boost::movelib::adaptive_sort(elements, elements+element_count, order_type_less<T>());
boost::movelib::adaptive_sort(elements, elements+element_count, order_type_less());
break;
case SqrtHAdaptiveSort:
adaptive_sort_buffered( elements, element_count, order_type_less<T>()
adaptive_sort_buffered( elements, element_count, order_type_less()
, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
break;
case SqrtAdaptiveSort:
adaptive_sort_buffered( elements, element_count, order_type_less<T>()
adaptive_sort_buffered( elements, element_count, order_type_less()
, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
break;
case Sqrt2AdaptiveSort:
adaptive_sort_buffered( elements, element_count, order_type_less<T>()
adaptive_sort_buffered( elements, element_count, order_type_less()
, 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
break;
case QuartAdaptiveSort:
adaptive_sort_buffered( elements, element_count, order_type_less<T>()
adaptive_sort_buffered( elements, element_count, order_type_less()
, (element_count-1)/4+1);
break;
case NoBufMergeSort:
boost::movelib::bufferless_merge_sort(elements, elements+element_count, order_type_less<T>());
break;
case InplaceStableSort:
boost::movelib::inplace_stable_sort(elements, elements+element_count, order_type_less<T>());
boost::movelib::inplace_stable_sort(elements, elements+element_count, order_type_less());
break;
case SlowStableSort:
boost::movelib::detail_adaptive::slow_stable_sort(elements, elements+element_count, order_type_less<T>());
boost::movelib::detail_adaptive::slow_stable_sort(elements, elements+element_count, order_type_less());
break;
case HeapSort:
std::make_heap(elements, elements+element_count, order_type_less<T>());
std::sort_heap(elements, elements+element_count, order_type_less<T>());
std::make_heap(elements, elements+element_count, order_type_less());
std::sort_heap(elements, elements+element_count, order_type_less());
break;
}
timer.stop();

if(order_type::num_elements == element_count){
if(order_perf_type::num_elements == element_count){
std::printf(" Tmp Ok ");
} else{
std::printf(" Tmp KO ");
}
nanosecond_type new_clock = timer.elapsed().wall;

//std::cout << "Cmp:" << order_type::num_compare << " Cpy:" << order_type::num_copy; //for old compilers without ll size argument
std::printf("Cmp:%7.03f Cpy:%8.03f", double(order_type::num_compare)/element_count, double(order_type::num_copy)/element_count );
//std::cout << "Cmp:" << order_perf_type::num_compare << " Cpy:" << order_perf_type::num_copy; //for old compilers without ll size argument
std::printf("Cmp:%7.03f Cpy:%8.03f", double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );

double time = double(new_clock);

Expand All @@ -186,7 +181,7 @@ bool measure_algo(T *elements, std::size_t key_reps[], std::size_t element_count
, units
, prev_clock ? double(new_clock)/double(prev_clock): 1.0);
prev_clock = new_clock;
bool res = is_order_type_ordered(elements, element_count, alg != HeapSort && alg != NoBufMergeSort);
bool res = is_order_type_ordered(elements, element_count, alg != HeapSort);
return res;
}

Expand Down Expand Up @@ -229,9 +224,6 @@ bool measure_all(std::size_t L, std::size_t NK)
prev_clock = back_clock;
res = res && measure_algo(A,Keys,L,NK,InplaceStableSort, prev_clock);
//
prev_clock = back_clock;
res = res && measure_algo(A,Keys,L,NK,NoBufMergeSort, prev_clock);
//
//prev_clock = back_clock;
//res = res && measure_algo(A,Keys,L,NK,SlowStableSort, prev_clock);
//
Expand All @@ -247,56 +239,55 @@ bool measure_all(std::size_t L, std::size_t NK)
int main()
{
#ifndef BENCH_SORT_UNIQUE_VALUES
//measure_all<order_type>(101,1);
measure_all<order_type>(101,7);
measure_all<order_type>(101,31);
measure_all<order_perf_type>(101,1);
measure_all<order_perf_type>(101,7);
measure_all<order_perf_type>(101,31);
#endif
measure_all<order_type>(101,0);
measure_all<order_perf_type>(101,0);

//
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(1101,1);
measure_all<order_type>(1001,7);
measure_all<order_type>(1001,31);
measure_all<order_type>(1001,127);
measure_all<order_type>(1001,511);
measure_all<order_perf_type>(1101,1);
measure_all<order_perf_type>(1001,7);
measure_all<order_perf_type>(1001,31);
measure_all<order_perf_type>(1001,127);
measure_all<order_perf_type>(1001,511);
#endif
measure_all<order_type>(1001,0);
measure_all<order_perf_type>(1001,0);
//
#ifndef BENCH_SORT_SHORT
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(10001,65);
measure_all<order_type>(10001,255);
measure_all<order_type>(10001,1023);
measure_all<order_type>(10001,4095);
measure_all<order_type>(10001,0);
measure_all<order_perf_type>(10001,65);
measure_all<order_perf_type>(10001,255);
measure_all<order_perf_type>(10001,1023);
measure_all<order_perf_type>(10001,4095);
#endif
measure_all<order_perf_type>(10001,0);

//
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(100001,511);
measure_all<order_type>(100001,2047);
measure_all<order_type>(100001,8191);
measure_all<order_type>(100001,32767);
measure_all<order_perf_type>(100001,511);
measure_all<order_perf_type>(100001,2047);
measure_all<order_perf_type>(100001,8191);
measure_all<order_perf_type>(100001,32767);
#endif
measure_all<order_type>(100001,0);
measure_all<order_perf_type>(100001,0);

//
//#ifdef NDEBUG
#ifdef NDEBUG
#ifndef BENCH_SORT_UNIQUE_VALUES
measure_all<order_type>(1000001,1);
measure_all<order_type>(1000001,1024);
measure_all<order_type>(1000001,32768);
measure_all<order_type>(1000001,524287);
measure_all<order_perf_type>(1000001,1);
measure_all<order_perf_type>(1000001,1024);
measure_all<order_perf_type>(1000001,32768);
measure_all<order_perf_type>(1000001,524287);
#endif
measure_all<order_type>(1000001,0);
measure_all<order_type>(1500001,0);
//measure_all<order_type>(10000001,0);
//#endif //NDEBUG
measure_all<order_perf_type>(1000001,0);
measure_all<order_perf_type>(1500001,0);
#endif //NDEBUG

#endif //#ifndef BENCH_SORT_SHORT

//measure_all<order_type>(100000001,0);
//measure_all<order_perf_type>(100000001,0);

return 0;
}
283 changes: 283 additions & 0 deletions test/inplace_merge_test.cpp
View file
@@ -0,0 +1,283 @@
//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2016-2016.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/move for documentation.
//
//////////////////////////////////////////////////////////////////////////////

//#define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
#define BOOST_MOVE_ADAPTIVE_SORT_STATS

#include "order_type.hpp"

#include <iostream> //std::cout
#include <boost/config.hpp>

#include <boost/move/algo/detail/adaptive_sort_merge.hpp>
#include <boost/move/core.hpp>
#include <boost/move/unique_ptr.hpp>
#include <boost/move/make_unique.hpp>

#include <boost/move/detail/type_traits.hpp>
#include <boost/core/lightweight_test.hpp>

#include <cstddef>

const std::size_t BlockSize = 7u;

#if defined(BOOST_MSVC)
#pragma warning (disable : 4267)
#endif


const std::size_t left_merge = 0;
const std::size_t buf_merge = 1;
const std::size_t unbuf_merge= 2;
const std::size_t max_merge = 3;

template<class Op>
void alternating_test(
const std::size_t NumBlocksA,
const std::size_t NumBlocksB,
const std::size_t ExtraA,
const std::size_t ExtraB,
Op op)
{
using namespace boost::movelib::detail_adaptive;


const std::size_t DataSize = ExtraA + NumBlocksA*BlockSize + NumBlocksB*BlockSize + ExtraB;
const std::size_t KeySize = NumBlocksA + NumBlocksB + 1;
const std::size_t HdrSize = BlockSize + KeySize;
const std::size_t ArraySize = HdrSize + DataSize;

boost::movelib::unique_ptr<order_move_type[]> testarray(boost::movelib::make_unique<order_move_type[]>(ArraySize));


for(std::size_t szt_merge = 0; szt_merge != max_merge; ++szt_merge){
//Order keys
for (std::size_t szt_i = 0u; szt_i != KeySize; ++szt_i) {
testarray[szt_i].key = szt_i;
testarray[szt_i].val = std::size_t(-1);
}

//Order buffer
for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i) {
testarray[KeySize+szt_i].key = std::size_t(-1);
testarray[KeySize+szt_i].val = szt_i;
}

//Block A
std::size_t szt_k = 0;
for (std::size_t szt_i = 0u; szt_i != ExtraA; ++szt_i) {
testarray[HdrSize+szt_k].key = (szt_k/2)*2;
testarray[HdrSize+szt_k].val = szt_k & 1;
++szt_k;
}

for (std::size_t szt_b = 0u; szt_b != NumBlocksA; ++szt_b)
for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i) {
testarray[HdrSize+szt_k].key = (szt_k/2)*2;
testarray[HdrSize+szt_k].val = szt_k & 1;
++szt_k;
}

//Block B
std::size_t szt_l = 0;
for (std::size_t szt_b = 0u, szt_t = 0; szt_b != NumBlocksB; ++szt_b)
for (std::size_t szt_i = 0u; szt_i != BlockSize; ++szt_i, ++szt_t) {
testarray[HdrSize+szt_k].key = (szt_l/2)*2+1;
testarray[HdrSize+szt_k].val = szt_l & 1;
++szt_k;
++szt_l;
}

for (std::size_t szt_i = 0u; szt_i != ExtraB; ++szt_i) {
testarray[HdrSize+szt_k].key = (szt_l/2)*2+1;
testarray[HdrSize+szt_k].val = szt_l & 1;
++szt_k;
++szt_l;
}

if(szt_merge == left_merge){
//Merge Left
op_merge_blocks_left
( testarray.get(), order_type_less()
, testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
, order_type_less(), op );
BOOST_TEST( is_order_type_ordered(testarray.get()+KeySize, DataSize) );
BOOST_TEST( is_key(testarray.get(), KeySize) );
BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
|| is_buffer(testarray.get()+ KeySize+DataSize, BlockSize) ));
}
else if(szt_merge == buf_merge){
//Merge with buf
op_merge_blocks_with_buf
( testarray.get(), order_type_less()
, testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
, order_type_less(), op, testarray.get()+KeySize );
BOOST_TEST( is_order_type_ordered(testarray.get()+HdrSize, DataSize) );
BOOST_TEST( is_key(testarray.get(), KeySize) );
BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
|| is_buffer(testarray.get()+ KeySize, BlockSize) ));
}
else if(szt_merge == unbuf_merge){
//Merge Left
merge_blocks_bufferless
( testarray.get(), order_type_less()
, testarray.get()+HdrSize, BlockSize, ExtraA, NumBlocksA, NumBlocksB, ExtraB
, order_type_less());
BOOST_TEST( is_order_type_ordered(testarray.get()+HdrSize, DataSize) );
BOOST_TEST( is_key(testarray.get(), KeySize) );
BOOST_TEST(( !boost::move_detail::is_same<Op, boost::movelib::swap_op>::value
|| is_buffer(testarray.get()+ KeySize, BlockSize) ));
}
}
}

int main()
{
{
const std::size_t NumBlocksA = 3u;
const std::size_t NumBlocksB = 3u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = ExtraA;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 3u;
const std::size_t NumBlocksB = 3u;
const std::size_t ExtraA = 0u;
const std::size_t ExtraB = BlockSize/2;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 3u;
const std::size_t NumBlocksB = 3u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 3u;
const std::size_t NumBlocksB = 3u;
const std::size_t ExtraA = 0;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 6u;
const std::size_t NumBlocksB = 3u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = ExtraA;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 6u;
const std::size_t NumBlocksB = 3u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 3u;
const std::size_t NumBlocksB = 5u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = ExtraA;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 3u;
const std::size_t NumBlocksB = 5u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 0u;
const std::size_t NumBlocksB = 0u;
const std::size_t ExtraA = 0;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 0u;
const std::size_t NumBlocksB = 0u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 0u;
const std::size_t NumBlocksB = 0u;
const std::size_t ExtraA = 0;
const std::size_t ExtraB = BlockSize/2;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
//
{
const std::size_t NumBlocksA = 0u;
const std::size_t NumBlocksB = 1u;
const std::size_t ExtraA = 0;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 1u;
const std::size_t NumBlocksB = 0u;
const std::size_t ExtraA = 0;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 1u;
const std::size_t NumBlocksB = 0u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 0u;
const std::size_t NumBlocksB = 1u;
const std::size_t ExtraA = BlockSize/2;
const std::size_t ExtraB = 0;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 1u;
const std::size_t NumBlocksB = 0u;
const std::size_t ExtraA = 0;
const std::size_t ExtraB = BlockSize/2;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}
{
const std::size_t NumBlocksA = 0u;
const std::size_t NumBlocksB = 1u;
const std::size_t ExtraA = 0;
const std::size_t ExtraB = BlockSize/2;
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::move_op());
alternating_test(NumBlocksA, NumBlocksB, ExtraA, ExtraB, boost::movelib::swap_op());
}

return ::boost::report_errors();
}
113 changes: 100 additions & 13 deletions test/order_type.hpp
View file
Expand Up @@ -13,70 +13,157 @@
#define BOOST_MOVE_TEST_ORDER_TYPE_HPP

#include <boost/config.hpp>
#include <boost/move/core.hpp>
#include <cstddef>
#include <cstdio>

struct order_type
struct order_perf_type
{
public:
std::size_t key;
std::size_t val;

order_type()
order_perf_type()
{
++num_elements;
}

order_type(const order_type& other)
order_perf_type(const order_perf_type& other)
: key(other.key), val(other.val)
{
++num_elements;
++num_copy;
}

order_type & operator=(const order_type& other)
order_perf_type & operator=(const order_perf_type& other)
{
++num_copy;
key = other.key;
val = other.val;
return *this;
}

~order_type ()
~order_perf_type ()
{
--num_elements;
}

static void reset_stats()
{
num_compare=0;
num_copy=0;
}

friend bool operator< (const order_perf_type& left, const order_perf_type& right)
{ ++num_compare; return left.key < right.key; }

static boost::ulong_long_type num_compare;
static boost::ulong_long_type num_copy;
static boost::ulong_long_type num_elements;
};

boost::ulong_long_type order_type::num_compare = 0;
boost::ulong_long_type order_type::num_copy = 0;
boost::ulong_long_type order_type::num_elements = 0;
boost::ulong_long_type order_perf_type::num_compare = 0;
boost::ulong_long_type order_perf_type::num_copy = 0;
boost::ulong_long_type order_perf_type::num_elements = 0;


struct order_move_type
{
BOOST_MOVABLE_BUT_NOT_COPYABLE(order_move_type)

public:
std::size_t key;
std::size_t val;

order_move_type()
: key(0u), val(0u)
{}

order_move_type(BOOST_RV_REF(order_move_type) other)
: key(other.key), val(other.val)
{
other.key = other.val = std::size_t(-1);
}

order_move_type & operator=(BOOST_RV_REF(order_move_type) other)
{
key = other.key;
val = other.val;
other.key = other.val = std::size_t(-2);
return *this;
}

friend bool operator< (const order_move_type& left, const order_move_type& right)
{ return left.key < right.key; }

~order_move_type ()
{
key = val = std::size_t(-3);
}
};

template<class T>
struct order_type_less
{
bool operator()(const T &a,T const &b) const
{ ++order_type::num_compare; return a.key < b.key; }
template<class T>
bool operator()(const T &a, T const &b) const
{ return a < b; }
};

template<class T>
inline bool is_order_type_ordered(T *elements, std::size_t element_count, bool stable = true)
{
for(std::size_t i = 1; i < element_count; ++i){
if(order_type_less<T>()(elements[i], elements[i-1])){
if(order_type_less()(elements[i], elements[i-1])){
std::printf("\n Ord KO !!!!");
return false;
}
if( stable && !(order_type_less<T>()(elements[i-1], elements[i])) && (elements[i-1].val > elements[i].val) ){
if( stable && !(order_type_less()(elements[i-1], elements[i])) && (elements[i-1].val > elements[i].val) ){
std::printf("\n Stb KO !!!! ");
return false;
}
}
return true;
}

namespace boost {
namespace movelib {
namespace detail_adaptive {



}}}

template<class T>
inline bool is_key(T *elements, std::size_t element_count)
{
for(std::size_t i = 1; i < element_count; ++i){
if(elements[i].key >= element_count){
std::printf("\n Key.key KO !!!!");
return false;
}
if(elements[i].val != std::size_t(-1)){
std::printf("\n Key.val KO !!!!");
return false;
}
}
return true;
}

template<class T>
inline bool is_buffer(T *elements, std::size_t element_count)
{
for(std::size_t i = 1; i < element_count; ++i){
if(elements[i].key != std::size_t(-1)){
std::printf("\n Buf.key KO !!!!");
return false;
}
if(elements[i].val >= element_count){
std::printf("\n Buf.val KO !!!!");
return false;
}
}
return true;
}


#endif //BOOST_MOVE_TEST_ORDER_TYPE_HPP
23 changes: 23 additions & 0 deletions test/random_shuffle.hpp
View file
@@ -0,0 +1,23 @@
#ifndef BOOST_MOVE_TEST_RANDOM_SHUFFLE_HPP
#define BOOST_MOVE_TEST_RANDOM_SHUFFLE_HPP


#include <boost/move/adl_move_swap.hpp>
#include <boost/move/detail/iterator_traits.hpp>
#include <stdlib.h>

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last )
{
typedef typename boost::movelib::iterator_traits<RandomIt>::difference_type difference_type;
difference_type n = last - first;
for (difference_type i = n-1; i > 0; --i) {
difference_type j = std::rand() % (i+1);
if(j != i) {
boost::adl_move_swap(first[i], first[j]);
}
}
}


#endif// BOOST_MOVE_TEST_RANDOM_SHUFFLE_HPP