1//----------------------------------------------------------------------------
2/// @file move_blocks.hpp
3/// @brief contains the class move_blocks, which is part of the
4/// block_indirect_sort algorithm
5///
6/// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n
7/// Distributed under the Boost Software License, Version 1.0.\n
8/// ( See accompanying file LICENSE_1_0.txt or copy at
9/// http://www.boost.org/LICENSE_1_0.txt )
10/// @version 0.1
11///
12/// @remarks
13//-----------------------------------------------------------------------------
14#ifndef __BOOST_SORT_PARALLEL_DETAIL_MOVE_BLOCKS_HPP
15#define __BOOST_SORT_PARALLEL_DETAIL_MOVE_BLOCKS_HPP
16
17#include <atomic>
18#include <ciso646>
19#include <future>
20#include <iostream>
21#include <iterator>
22#include <boost/sort/block_indirect_sort/blk_detail/backbone.hpp>
23
24namespace boost
25{
26namespace sort
27{
28namespace blk_detail
29{
30//----------------------------------------------------------------------------
31// USING SENTENCES
32//----------------------------------------------------------------------------
33namespace bsc = boost::sort::common;
34//
35///---------------------------------------------------------------------------
36/// @struct move_blocks
37/// @brief This class move the blocks, trnasforming a logical sort by an index,
38/// in physical sort
39//----------------------------------------------------------------------------
40template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare>
41struct move_blocks
42{
43 //-------------------------------------------------------------------------
44 // D E F I N I T I O N S
45 //-------------------------------------------------------------------------
46 typedef move_blocks<Block_size, Group_size, Iter_t, Compare> this_type;
47 typedef typename std::iterator_traits<Iter_t>::value_type value_t;
48 typedef std::atomic<uint32_t> atomic_t;
49 typedef bsc::range<size_t> range_pos;
50 typedef bsc::range<Iter_t> range_it;
51 typedef bsc::range<value_t *> range_buf;
52 typedef std::function<void(void)> function_t;
53 typedef backbone<Block_size, Iter_t, Compare> backbone_t;
54
55 //------------------------------------------------------------------------
56 // V A R I A B L E S
57 //------------------------------------------------------------------------
58 // Object with the elements to sort and all internal data structures of the
59 // algorithm
60 backbone_t &bk;
61
62 //------------------------------------------------------------------------
63 // F U N C T I O N S
64 //------------------------------------------------------------------------
65 move_blocks(backbone_t &bkb);
66
67 void move_sequence(const std::vector<size_t> &init_sequence);
68
69 void move_long_sequence(const std::vector<size_t> &init_sequence);
70 //
71 //------------------------------------------------------------------------
72 // function : function_move_sequence
73 /// @brief create a function_t with a call to move_sequence, and insert
74 /// in the stack of the backbone
75 ///
76 /// @param sequence :sequence of positions for to move the blocks
77 /// @param counter : atomic variable which is decremented when finish
78 /// the function. This variable is used for to know
79 /// when are finished all the function_t created
80 /// inside an object
81 /// @param error : global indicator of error.
82 //------------------------------------------------------------------------
83 void function_move_sequence(std::vector<size_t> &sequence,
84 atomic_t &counter, bool &error)
85 {
86 bscu::atomic_add(at_var&: counter, num: 1);
87 function_t f1 = [this, sequence, &counter, &error]( ) -> void
88 {
89 if (not error)
90 {
91 try
92 {
93 this->move_sequence (init_sequence: sequence);
94 }
95 catch (std::bad_alloc &)
96 {
97 error = true;
98 };
99 }
100 bscu::atomic_sub (at_var&: counter, num: 1);
101 };
102 bk.works.emplace_back(f1);
103 }
104
105 //
106 //------------------------------------------------------------------------
107 // function : function_move_long_sequence
108 /// @brief create a function_t with a call to move_long_sequence, and
109 /// insert in the stack of the backbone
110 //
111 /// @param sequence :sequence of positions for to move the blocks
112 /// @param counter : atomic variable which is decremented when finish
113 /// the function. This variable is used for to know
114 /// when are finished all the function_t created
115 /// inside an object
116 /// @param error : global indicator of error.
117 //------------------------------------------------------------------------
118 void function_move_long_sequence(std::vector<size_t> &sequence,
119 atomic_t &counter, bool &error)
120 {
121 bscu::atomic_add(at_var&: counter, num: 1);
122 function_t f1 = [this, sequence, &counter, &error]( ) -> void
123 {
124 if (not error)
125 {
126 try
127 {
128 this->move_long_sequence (init_sequence: sequence);
129 }
130 catch (std::bad_alloc &)
131 {
132 error = true;
133 };
134 }
135 bscu::atomic_sub (at_var&: counter, num: 1);
136 };
137 bk.works.emplace_back(f1);
138 }
139 ;
140//---------------------------------------------------------------------------
141}; // end of struct move_blocks
142//---------------------------------------------------------------------------
143//
144//############################################################################
145// ##
146// ##
147// N O N I N L I N E F U N C T I O N S ##
148// ##
149// ##
150//############################################################################
151//
152//-------------------------------------------------------------------------
153// function : move_blocks
154/// @brief constructor of the class for to move the blocks to their true
155/// position obtained from the index
156//
157/// @param bkb : backbone with the index and the blocks
158//-------------------------------------------------------------------------
159template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare>
160move_blocks<Block_size, Group_size, Iter_t, Compare>
161::move_blocks(backbone_t &bkb) : bk(bkb)
162{
163 std::vector<std::vector<size_t> > vsequence;
164 vsequence.reserve(n: bk.index.size() >> 1);
165 std::vector<size_t> sequence;
166 atomic_t counter(0);
167
168 size_t pos_index_ini = 0, pos_index_src = 0, pos_index_dest = 0;
169 while (pos_index_ini < bk.index.size())
170 {
171 while (pos_index_ini < bk.index.size()
172 and bk.index[pos_index_ini].pos() == pos_index_ini)
173 {
174 ++pos_index_ini;
175 };
176
177 if (pos_index_ini == bk.index.size()) break;
178
179 sequence.clear();
180 pos_index_src = pos_index_dest = pos_index_ini;
181 sequence.push_back(x: pos_index_ini);
182
183 while (bk.index[pos_index_dest].pos() != pos_index_ini)
184 {
185 pos_index_src = bk.index[pos_index_dest].pos();
186 sequence.push_back(x: pos_index_src);
187
188 bk.index[pos_index_dest].set_pos(pos_index_dest);
189 pos_index_dest = pos_index_src;
190 };
191
192 bk.index[pos_index_dest].set_pos(pos_index_dest);
193 vsequence.push_back(x: sequence);
194
195 if (sequence.size() < Group_size)
196 {
197 function_move_sequence(sequence&: vsequence.back(), counter, error&: bk.error);
198 }
199 else
200 {
201 function_move_long_sequence(sequence&: vsequence.back(), counter, error&: bk.error);
202 };
203 };
204 bk.exec(counter);
205}
206;
207//
208//-------------------------------------------------------------------------
209// function : move_sequence
210/// @brief move the blocks, following the positions of the init_sequence
211//
212/// @param init_sequence : vector with the positions from and where move the
213/// blocks
214//-------------------------------------------------------------------------
215template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare>
216void move_blocks<Block_size, Group_size, Iter_t, Compare>
217::move_sequence(const std::vector<size_t> &init_sequence)
218{
219 range_buf rbuf = bk.get_range_buf();
220 size_t pos_range2 = init_sequence[0];
221
222 range_it range2 = bk.get_range(pos_range2);
223 move_forward(rbuf, range2);
224
225 for (size_t i = 1; i < init_sequence.size(); ++i)
226 {
227 pos_range2 = init_sequence[i];
228 range_it range1(range2);
229 range2 = bk.get_range(pos_range2);
230 move_forward(range1, range2);
231 };
232 move_forward(range2, rbuf);
233};
234//
235//-------------------------------------------------------------------------
236// function : move_long_sequence
237/// @brief move the blocks, following the positions of the init_sequence.
238/// if the sequence is greater than Group_size, it is divided in small
239/// sequences, creating function_t elements, for to be inserted in the
240/// concurrent stack
241//
242/// @param init_sequence : vector with the positions from and where move the
243/// blocks
244//-------------------------------------------------------------------------
245template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare>
246void move_blocks<Block_size, Group_size, Iter_t, Compare>
247::move_long_sequence(const std::vector<size_t> &init_sequence)
248{
249 if (init_sequence.size() < Group_size) return move_sequence(init_sequence);
250
251 size_t npart = (init_sequence.size() + Group_size - 1) / Group_size;
252 size_t size_part = init_sequence.size() / npart;
253 atomic_t son_counter(0);
254
255 std::vector<size_t> sequence;
256 sequence.reserve(n: size_part);
257
258 std::vector<size_t> index_seq;
259 index_seq.reserve(n: npart);
260
261 auto it_pos = init_sequence.begin();
262 for (size_t i = 0; i < (npart - 1); ++i, it_pos += size_part)
263 {
264 sequence.assign(first: it_pos, last: it_pos + size_part);
265 index_seq.emplace_back(args: *(it_pos + size_part - 1));
266 function_move_sequence(sequence, counter&: son_counter, error&: bk.error);
267 };
268
269 sequence.assign(first: it_pos, last: init_sequence.end());
270 index_seq.emplace_back(args: init_sequence.back());
271 function_move_sequence(sequence, counter&: son_counter, error&: bk.error);
272
273 bk.exec(son_counter);
274 if (bk.error) return;
275 move_long_sequence(init_sequence: index_seq);
276}
277
278//
279//****************************************************************************
280}; // End namespace blk_detail
281}; // End namespace sort
282}; // End namespace boost
283//****************************************************************************
284//
285#endif
286

source code of boost/libs/sort/include/boost/sort/block_indirect_sort/blk_detail/move_blocks.hpp