//----------------------------------------------------------------------------
|
/// @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
|
