diff options
Diffstat (limited to 'boost/sort/block_indirect_sort/blk_detail/move_blocks.hpp')
| -rw-r--r-- | boost/sort/block_indirect_sort/blk_detail/move_blocks.hpp | 284 |
1 files changed, 284 insertions, 0 deletions
diff --git a/boost/sort/block_indirect_sort/blk_detail/move_blocks.hpp b/boost/sort/block_indirect_sort/blk_detail/move_blocks.hpp new file mode 100644 index 0000000000..6b556bcf47 --- /dev/null +++ b/boost/sort/block_indirect_sort/blk_detail/move_blocks.hpp @@ -0,0 +1,284 @@ +//---------------------------------------------------------------------------- +/// @file move_blocks.hpp +/// @brief contains the class move_blocks, which is part of the +/// block_indirect_sort algorithm +/// +/// @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_MOVE_BLOCKS_HPP +#define __BOOST_SORT_PARALLEL_DETAIL_MOVE_BLOCKS_HPP + +#include <atomic> +#include <boost/sort/block_indirect_sort/blk_detail/backbone.hpp> +#include <future> +#include <iostream> +#include <iterator> + +namespace boost +{ +namespace sort +{ +namespace blk_detail +{ +//---------------------------------------------------------------------------- +// USING SENTENCES +//---------------------------------------------------------------------------- +namespace bsc = boost::sort::common; +// +///--------------------------------------------------------------------------- +/// @struct move_blocks +/// @brief This class move the blocks, trnasforming a logical sort by an index, +/// in physical sort +//---------------------------------------------------------------------------- +template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare> +struct move_blocks +{ + //------------------------------------------------------------------------- + // D E F I N I T I O N S + //------------------------------------------------------------------------- + typedef move_blocks<Block_size, Group_size, Iter_t, Compare> this_type; + typedef typename std::iterator_traits<Iter_t>::value_type value_t; + typedef std::atomic<uint32_t> atomic_t; + typedef bsc::range<size_t> range_pos; + typedef bsc::range<Iter_t> range_it; + typedef bsc::range<value_t *> range_buf; + typedef std::function<void(void)> function_t; + typedef backbone<Block_size, Iter_t, Compare> backbone_t; + + //------------------------------------------------------------------------ + // V A R I A B L E S + //------------------------------------------------------------------------ + // Object with the elements to sort and all internal data structures of the + // algorithm + backbone_t &bk; + + //------------------------------------------------------------------------ + // F U N C T I O N S + //------------------------------------------------------------------------ + move_blocks(backbone_t &bkb); + + void move_sequence(const std::vector<size_t> &init_sequence); + + void move_long_sequence(const std::vector<size_t> &init_sequence); + // + //------------------------------------------------------------------------ + // function : function_move_sequence + /// @brief create a function_t with a call to move_sequence, and insert + /// in the stack of the backbone + /// + /// @param sequence :sequence of positions for to move the blocks + /// @param counter : atomic variable which is decremented when finish + /// the function. This variable is used for to know + /// when are finished all the function_t created + /// inside an object + /// @param error : global indicator of error. + //------------------------------------------------------------------------ + void function_move_sequence(std::vector<size_t> &sequence, + atomic_t &counter, bool &error) + { + bscu::atomic_add(counter, 1); + function_t f1 = [this, sequence, &counter, &error]( ) -> void + { + if (not error) + { + try + { + this->move_sequence (sequence); + } + catch (std::bad_alloc &) + { + error = true; + }; + } + bscu::atomic_sub (counter, 1); + }; + bk.works.emplace_back(f1); + } + + // + //------------------------------------------------------------------------ + // function : function_move_long_sequence + /// @brief create a function_t with a call to move_long_sequence, and + /// insert in the stack of the backbone + // + /// @param sequence :sequence of positions for to move the blocks + /// @param counter : atomic variable which is decremented when finish + /// the function. This variable is used for to know + /// when are finished all the function_t created + /// inside an object + /// @param error : global indicator of error. + //------------------------------------------------------------------------ + void function_move_long_sequence(std::vector<size_t> &sequence, + atomic_t &counter, bool &error) + { + bscu::atomic_add(counter, 1); + function_t f1 = [this, sequence, &counter, &error]( ) -> void + { + if (not error) + { + try + { + this->move_long_sequence (sequence); + } + catch (std::bad_alloc &) + { + error = true; + }; + } + bscu::atomic_sub (counter, 1); + }; + bk.works.emplace_back(f1); + } + ; +//--------------------------------------------------------------------------- +}; // end of struct move_blocks +//--------------------------------------------------------------------------- +// +//############################################################################ +// ## +// ## +// N O N I N L I N E F U N C T I O N S ## +// ## +// ## +//############################################################################ +// +//------------------------------------------------------------------------- +// function : move_blocks +/// @brief constructor of the class for to move the blocks to their true +/// position obtained from the index +// +/// @param bkb : backbone with the index and the blocks +//------------------------------------------------------------------------- +template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare> +move_blocks<Block_size, Group_size, Iter_t, Compare> +::move_blocks(backbone_t &bkb) : bk(bkb) +{ + std::vector<std::vector<size_t> > vsequence; + vsequence.reserve(bk.index.size() >> 1); + std::vector<size_t> sequence; + atomic_t counter(0); + + size_t pos_index_ini = 0, pos_index_src = 0, pos_index_dest = 0; + while (pos_index_ini < bk.index.size()) + { + while (pos_index_ini < bk.index.size() + and bk.index[pos_index_ini].pos() == pos_index_ini) + { + ++pos_index_ini; + }; + + if (pos_index_ini == bk.index.size()) break; + + sequence.clear(); + pos_index_src = pos_index_dest = pos_index_ini; + sequence.push_back(pos_index_ini); + + while (bk.index[pos_index_dest].pos() != pos_index_ini) + { + pos_index_src = bk.index[pos_index_dest].pos(); + sequence.push_back(pos_index_src); + + bk.index[pos_index_dest].set_pos(pos_index_dest); + pos_index_dest = pos_index_src; + }; + + bk.index[pos_index_dest].set_pos(pos_index_dest); + vsequence.push_back(sequence); + + if (sequence.size() < Group_size) + { + function_move_sequence(vsequence.back(), counter, bk.error); + } + else + { + function_move_long_sequence(vsequence.back(), counter, bk.error); + }; + }; + bk.exec(counter); +} +; +// +//------------------------------------------------------------------------- +// function : move_sequence +/// @brief move the blocks, following the positions of the init_sequence +// +/// @param init_sequence : vector with the positions from and where move the +/// blocks +//------------------------------------------------------------------------- +template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare> +void move_blocks<Block_size, Group_size, Iter_t, Compare> +::move_sequence(const std::vector<size_t> &init_sequence) +{ + range_buf rbuf = bk.get_range_buf(); + size_t pos_range2 = init_sequence[0]; + + range_it range2 = bk.get_range(pos_range2); + move_forward(rbuf, range2); + + for (size_t i = 1; i < init_sequence.size(); ++i) + { + pos_range2 = init_sequence[i]; + range_it range1(range2); + range2 = bk.get_range(pos_range2); + move_forward(range1, range2); + }; + move_forward(range2, rbuf); +}; +// +//------------------------------------------------------------------------- +// function : move_long_sequence +/// @brief move the blocks, following the positions of the init_sequence. +/// if the sequence is greater than Group_size, it is divided in small +/// sequences, creating function_t elements, for to be inserted in the +/// concurrent stack +// +/// @param init_sequence : vector with the positions from and where move the +/// blocks +//------------------------------------------------------------------------- +template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare> +void move_blocks<Block_size, Group_size, Iter_t, Compare> +::move_long_sequence(const std::vector<size_t> &init_sequence) +{ + if (init_sequence.size() < Group_size) return move_sequence(init_sequence); + + size_t npart = (init_sequence.size() + Group_size - 1) / Group_size; + size_t size_part = init_sequence.size() / npart; + atomic_t son_counter(0); + + std::vector<size_t> sequence; + sequence.reserve(size_part); + + std::vector<size_t> index_seq; + index_seq.reserve(npart); + + auto it_pos = init_sequence.begin(); + for (size_t i = 0; i < (npart - 1); ++i, it_pos += size_part) + { + sequence.assign(it_pos, it_pos + size_part); + index_seq.emplace_back(*(it_pos + size_part - 1)); + function_move_sequence(sequence, son_counter, bk.error); + }; + + sequence.assign(it_pos, init_sequence.end()); + index_seq.emplace_back(init_sequence.back()); + function_move_sequence(sequence, son_counter, bk.error); + + bk.exec(son_counter); + if (bk.error) return; + move_long_sequence(index_seq); +} + +// +//**************************************************************************** +}; // End namespace blk_detail +}; // End namespace sort +}; // End namespace boost +//**************************************************************************** +// +#endif |