diff options
Diffstat (limited to 'boost/sort/parallel_stable_sort/parallel_stable_sort.hpp')
| -rw-r--r-- | boost/sort/parallel_stable_sort/parallel_stable_sort.hpp | 270 |
1 files changed, 270 insertions, 0 deletions
diff --git a/boost/sort/parallel_stable_sort/parallel_stable_sort.hpp b/boost/sort/parallel_stable_sort/parallel_stable_sort.hpp new file mode 100644 index 0000000000..9df7dffd2a --- /dev/null +++ b/boost/sort/parallel_stable_sort/parallel_stable_sort.hpp @@ -0,0 +1,270 @@ +//---------------------------------------------------------------------------- +/// @file parallel_stable_sort.hpp +/// @brief This file contains the class parallel_stable_sort +/// +/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n +/// Distributed under the Boost Software License, Version 1.0.\n +/// ( See accompanying file LICENSE_1_0.txt or copy at +/// http://www.boost.org/LICENSE_1_0.txt ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#ifndef __BOOST_SORT_PARALLEL_DETAIL_PARALLEL_STABLE_SORT_HPP +#define __BOOST_SORT_PARALLEL_DETAIL_PARALLEL_STABLE_SORT_HPP + +#include <boost/sort/sample_sort/sample_sort.hpp> +#include <boost/sort/common/util/traits.hpp> +#include <functional> +#include <future> +#include <iterator> +#include <memory> +#include <type_traits> +#include <vector> + +namespace boost +{ +namespace sort +{ +namespace stable_detail +{ + +//--------------------------------------------------------------------------- +// USING SENTENCES +//--------------------------------------------------------------------------- +namespace bsc = boost::sort::common; +namespace bss = boost::sort::spin_detail; +using bsc::range; +using bsc::merge_half; +using boost::sort::sample_detail::sample_sort; +// +///--------------------------------------------------------------------------- +/// @struct parallel_stable_sort +/// @brief This a structure for to implement a parallel stable sort, exception +/// safe +//---------------------------------------------------------------------------- +template <class Iter_t, class Compare = compare_iter <Iter_t> > +struct parallel_stable_sort +{ + //------------------------------------------------------------------------- + // DEFINITIONS + //------------------------------------------------------------------------- + typedef value_iter<Iter_t> value_t; + + //------------------------------------------------------------------------- + // VARIABLES + //------------------------------------------------------------------------- + // Number of elements to sort + size_t nelem; + // Pointer to the auxiliary memory needed for the algorithm + value_t *ptr; + // Minimal number of elements for to be sorted in parallel mode + const size_t nelem_min = 1 << 16; + + //------------------------------------------------------------------------ + // F U N C T I O N S + //------------------------------------------------------------------------ + parallel_stable_sort (Iter_t first, Iter_t last) + : parallel_stable_sort (first, last, Compare(), + std::thread::hardware_concurrency()) { }; + + parallel_stable_sort (Iter_t first, Iter_t last, Compare cmp) + : parallel_stable_sort (first, last, cmp, + std::thread::hardware_concurrency()) { }; + + parallel_stable_sort (Iter_t first, Iter_t last, uint32_t num_thread) + : parallel_stable_sort (first, last, Compare(), num_thread) { }; + + parallel_stable_sort (Iter_t first, Iter_t last, Compare cmp, + uint32_t num_thread); + + // + //----------------------------------------------------------------------------- + // function : destroy_all + /// @brief The utility is to destroy the temporary buffer used in the + /// sorting process + //----------------------------------------------------------------------------- + void destroy_all() + { + if (ptr != nullptr) std::return_temporary_buffer(ptr); + }; + // + //----------------------------------------------------------------------------- + // function :~parallel_stable_sort + /// @brief destructor of the class. The utility is to destroy the temporary + /// buffer used in the sorting process + //----------------------------------------------------------------------------- + ~parallel_stable_sort() {destroy_all(); } ; +}; +// end struct parallel_stable_sort + +// +//############################################################################ +// ## +// ## +// N O N I N L I N E F U N C T I O N S ## +// ## +// ## +//############################################################################ +// +//----------------------------------------------------------------------------- +// function : parallel_stable_sort +/// @brief constructor of the class +/// +/// @param first : iterator to the first element of the range to sort +/// @param last : iterator after the last element to the range to sort +/// @param comp : object for to compare two elements pointed by Iter_t +/// iterators +/// @param nthread : Number of threads to use in the process. When this value +/// is lower than 2, the sorting is done with 1 thread +//----------------------------------------------------------------------------- +template <class Iter_t, class Compare> +parallel_stable_sort <Iter_t, Compare> +::parallel_stable_sort (Iter_t first, Iter_t last, Compare comp, + uint32_t nthread) : nelem(0), ptr(nullptr) +{ + range<Iter_t> range_initial(first, last); + assert(range_initial.valid()); + + nelem = range_initial.size(); + size_t nptr = (nelem + 1) >> 1; + + if (nelem < nelem_min or nthread < 2) + { + bss::spinsort<Iter_t, Compare> + (range_initial.first, range_initial.last, comp); + return; + }; + + //------------------- check if sort -------------------------------------- + bool sw = true; + for (Iter_t it1 = first, it2 = first + 1; + it2 != last and (sw = not comp(*it2, *it1)); it1 = it2++); + if (sw) return; + + //------------------- check if reverse sort --------------------------- + sw = true; + for (Iter_t it1 = first, it2 = first + 1; + it2 != last and (sw = comp(*it2, *it1)); it1 = it2++); + if (sw) + { + size_t nelem2 = nelem >> 1; + Iter_t it1 = first, it2 = last - 1; + for (size_t i = 0; i < nelem2; ++i) + std::swap(*(it1++), *(it2--)); + return; + }; + + ptr = std::get_temporary_buffer<value_t>(nptr).first; + if (ptr == nullptr) throw std::bad_alloc(); + + //--------------------------------------------------------------------- + // Parallel Process + //--------------------------------------------------------------------- + range<Iter_t> range_first(range_initial.first, range_initial.first + nptr); + + range<Iter_t> range_second(range_initial.first + nptr, range_initial.last); + + range<value_t *> range_buffer(ptr, ptr + nptr); + + try + { + sample_sort<Iter_t, Compare> + (range_initial.first, range_initial.first + nptr, + comp, nthread, range_buffer); + } catch (std::bad_alloc &) + { + destroy_all(); + throw std::bad_alloc(); + }; + + try + { + sample_sort<Iter_t, Compare> + (range_initial.first + nptr, + range_initial.last, comp, nthread, range_buffer); + } catch (std::bad_alloc &) + { + destroy_all(); + throw std::bad_alloc(); + }; + + range_buffer = move_forward(range_buffer, range_first); + range_initial = merge_half(range_initial, range_buffer, range_second, comp); +}; // end of constructor + +// +//**************************************************************************** +};// End namespace stable_detail +//**************************************************************************** +// + +//--------------------------------------------------------------------------- +// USING SENTENCES +//--------------------------------------------------------------------------- +namespace bsc = boost::sort::common; +namespace bscu = bsc::util; +namespace bss = boost::sort::spin_detail; +using bsc::range; +using bsc::merge_half; +// +//############################################################################ +// ## +// ## +// P A R A L L E L _ S T A B L E _ S O R T ## +// ## +// ## +//############################################################################ +// +//----------------------------------------------------------------------------- +// function : parallel_stable_sort +/// @brief : parallel stable sort algorithm. +/// +/// @param first : iterator to the first element of the range to sort +/// @param last : iterator after the last element to the range to sort +//----------------------------------------------------------------------------- +template<class Iter_t> +void parallel_stable_sort(Iter_t first, Iter_t last) +{ + typedef bscu::compare_iter<Iter_t> Compare; + stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last); +}; +// +//----------------------------------------------------------------------------- +// function : parallel_stable_sort +/// @brief parallel stable sort. +/// +/// @param first : iterator to the first element of the range to sort +/// @param last : iterator after the last element to the range to sort +/// @param nthread : Number of threads to use in the process. When this value +/// is lower than 2, the sorting is done with 1 thread +//----------------------------------------------------------------------------- +template<class Iter_t> +void parallel_stable_sort(Iter_t first, Iter_t last, uint32_t nthread) +{ + typedef bscu::compare_iter<Iter_t> Compare; + stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, nthread); +}; +// +//----------------------------------------------------------------------------- +// function : parallel_stable_sort +/// @brief : parallel stable sort. +/// +/// @param first : iterator to the first element of the range to sort +/// @param last : iterator after the last element to the range to sort +/// @param comp : object for to compare two elements pointed by Iter_t +/// iterators +//----------------------------------------------------------------------------- +template <class Iter_t, class Compare, + bscu::enable_if_not_integral<Compare> * = nullptr> +void parallel_stable_sort(Iter_t first, Iter_t last, Compare comp) +{ + stable_detail::parallel_stable_sort<Iter_t, Compare>(first, last, comp); +}; +// +//**************************************************************************** +};// End namespace sort +};// End namespace boost +//**************************************************************************** +// +#endif |