123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292 |
- //----------------------------------------------------------------------------
- /// @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 with 2 parameters
- ///
- /// @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 with 3 parameters. The third is the number
- /// of threads
- ///
- /// @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 with 3 parameters. The thisrd is the
- /// comparison object
- ///
- /// @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);
- };
- //
- //-----------------------------------------------------------------------------
- // function : parallel_stable_sort
- /// @brief : parallel stable sort with 3 parameters.
- ///
- /// @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>
- void parallel_stable_sort (Iter_t first, Iter_t last, Compare comp,
- uint32_t nthread)
- {
- stable_detail::parallel_stable_sort<Iter_t, Compare>
- (first, last, comp, nthread);
- }
- //
- //****************************************************************************
- };// End namespace sort
- };// End namespace boost
- //****************************************************************************
- //
- #endif
|