111 lines
2.7 KiB
C++
111 lines
2.7 KiB
C++
// Copyright (C) 2012-2013 Vicente Botet
|
|
//
|
|
// 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)
|
|
|
|
#include <boost/config.hpp>
|
|
|
|
#define BOOST_THREAD_VERSION 4
|
|
#define BOOST_THREAD_PROVIDES_EXECUTORS
|
|
#define BOOST_THREAD_USES_LOG_THREAD_ID
|
|
#define BOOST_THREAD_QUEUE_DEPRECATE_OLD
|
|
#if ! defined BOOST_NO_CXX11_DECLTYPE
|
|
#define BOOST_RESULT_OF_USE_DECLTYPE
|
|
#endif
|
|
|
|
#include <boost/thread/executors/basic_thread_pool.hpp>
|
|
#include <boost/thread/future.hpp>
|
|
#if defined(BOOST_THREAD_PROVIDES_VARIADIC_THREAD)
|
|
|
|
#include <numeric>
|
|
#include <algorithm>
|
|
#include <functional>
|
|
#include <iostream>
|
|
#include <list>
|
|
|
|
template<typename T>
|
|
struct sorter
|
|
{
|
|
boost::basic_thread_pool pool;
|
|
typedef std::list<T> return_type;
|
|
|
|
std::list<T> do_sort(std::list<T> chunk_data)
|
|
{
|
|
if(chunk_data.empty())
|
|
{
|
|
return chunk_data;
|
|
}
|
|
|
|
std::list<T> result;
|
|
result.splice(result.begin(),chunk_data, chunk_data.begin());
|
|
T const& partition_val=*result.begin();
|
|
|
|
typename std::list<T>::iterator divide_point=
|
|
std::partition(chunk_data.begin(), chunk_data.end(), [&](T const& val){return val<partition_val;});
|
|
|
|
std::list<T> new_lower_chunk;
|
|
new_lower_chunk.splice(new_lower_chunk.end(), chunk_data, chunk_data.begin(), divide_point);
|
|
|
|
boost::future<std::list<T> > new_lower = boost::async(pool, &sorter::do_sort, this, std::move(new_lower_chunk));
|
|
//boost::future<std::list<T> > new_lower = boost::async<return_type>(pool, &sorter::do_sort, this, std::move(new_lower_chunk));
|
|
|
|
std::list<T> new_higher(do_sort(chunk_data));
|
|
|
|
result.splice(result.end(),new_higher);
|
|
while(!new_lower.is_ready())
|
|
{
|
|
pool.schedule_one_or_yield();
|
|
}
|
|
|
|
result.splice(result.begin(),new_lower.get());
|
|
return result;
|
|
}
|
|
};
|
|
|
|
|
|
template<typename T>
|
|
std::list<T> parallel_quick_sort(std::list<T>& input)
|
|
{
|
|
if(input.empty())
|
|
{
|
|
return input;
|
|
}
|
|
sorter<T> s;
|
|
|
|
return s.do_sort(input);
|
|
}
|
|
|
|
|
|
int main()
|
|
{
|
|
try
|
|
{
|
|
const int s = 101;
|
|
std::list<int> lst;
|
|
for (int i=0; i<s;++i)
|
|
lst.push_back(100-i);
|
|
std::list<int> r = parallel_quick_sort(lst);
|
|
for (std::list<int>::const_iterator it=r.begin(); it != r.end(); ++it)
|
|
std::cout << *it << std::endl;
|
|
|
|
}
|
|
catch (std::exception& ex)
|
|
{
|
|
std::cout << "ERROR= " << ex.what() << "" << std::endl;
|
|
return 1;
|
|
}
|
|
catch (...)
|
|
{
|
|
std::cout << " ERROR= exception thrown" << std::endl;
|
|
return 2;
|
|
}
|
|
return 0;
|
|
}
|
|
#else
|
|
//#warning "This compiler doesn't supports variadics and move semantics"
|
|
int main()
|
|
{
|
|
return 0;
|
|
}
|
|
#endif
|