1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
//----------------------------------------------------------------------------
/// @file backbone.hpp
/// @brief This file constains the class backbone, 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_BACKBONE_HPP
#define __BOOST_SORT_PARALLEL_DETAIL_BACKBONE_HPP
#include <atomic>
#include <boost/sort/pdqsort/pdqsort.hpp>
#include <boost/sort/common/util/atomic.hpp>
#include <boost/sort/common/util/algorithm.hpp>
#include <boost/sort/common/stack_cnc.hpp>
#include <future>
#include <iostream>
#include <iterator>
#include <boost/sort/block_indirect_sort/blk_detail/block.hpp>
namespace boost
{
namespace sort
{
namespace blk_detail
{
//---------------------------------------------------------------------------
// USING SENTENCES
//---------------------------------------------------------------------------
namespace bsc = boost::sort::common;
namespace bscu = bsc::util;
using bsc::stack_cnc;
using bsc::range;
///---------------------------------------------------------------------------
/// @struct backbone
/// @brief This contains all the information shared betwen the classes of the
/// block indirect sort algorithm
//----------------------------------------------------------------------------
template < uint32_t Block_size, class Iter_t, class Compare >
struct backbone
{
//-------------------------------------------------------------------------
// D E F I N I T I O N S
//-------------------------------------------------------------------------
typedef typename std::iterator_traits< Iter_t >::value_type value_t;
typedef std::atomic< uint32_t > atomic_t;
typedef range< size_t > range_pos;
typedef range< Iter_t > range_it;
typedef range< value_t * > range_buf;
typedef std::function< void(void) > function_t;
typedef block< Block_size, Iter_t > block_t;
//------------------------------------------------------------------------
// V A R I A B L E S
//------------------------------------------------------------------------
// range with all the element to sort
range< Iter_t > global_range;
// index vector of block_pos elements
std::vector< block_pos > index;
// Number of elements to sort
size_t nelem;
// Number of blocks to sort
size_t nblock;
// Number of elements in the last block (tail)
size_t ntail;
// object for to compare two elements
Compare cmp;
// range of elements of the last block (tail)
range_it range_tail;
// thread local varible. It is a pointer to the buffer
static thread_local value_t *buf;
// concurrent stack where store the function_t elements
stack_cnc< function_t > works;
// global indicator of error
bool error;
//
//------------------------------------------------------------------------
// F U N C T I O N S
//------------------------------------------------------------------------
backbone (Iter_t first, Iter_t last, Compare comp);
//------------------------------------------------------------------------
// function : get_block
/// @brief obtain the block in the position pos
/// @param pos : position of the range
/// @return block required
//------------------------------------------------------------------------
block_t get_block (size_t pos) const
{
return block_t (global_range.first + (pos * Block_size));
};
//-------------------------------------------------------------------------
// function : get_range
/// @brief obtain the range in the position pos
/// @param pos : position of the range
/// @return range required
//-------------------------------------------------------------------------
range_it get_range (size_t pos) const
{
Iter_t it1 = global_range.first + (pos * Block_size);
Iter_t it2 =
(pos == (nblock - 1)) ? global_range.last : it1 + Block_size;
return range_it (it1, it2);
};
//-------------------------------------------------------------------------
// function : get_range_buf
/// @brief obtain the auxiliary buffer of the thread
//-------------------------------------------------------------------------
range_buf get_range_buf ( ) const
{
return range_buf (buf, buf + Block_size);
};
//-------------------------------------------------------------------------
// function : exec
/// @brief Initialize the thread local buffer with the ptr_buf pointer,
/// and begin with the execution of the functions stored in works
//
/// @param ptr_buf : Pointer to the memory assigned to the thread_local
/// buffer
/// @param counter : atomic counter for to invoke to the exec function
/// with only 1 parameter
//-------------------------------------------------------------------------
void exec (value_t *ptr_buf, atomic_t &counter)
{
buf = ptr_buf;
exec (counter);
};
void exec (atomic_t &counter);
//---------------------------------------------------------------------------
}; // end struct backbone
//---------------------------------------------------------------------------
//
//############################################################################
// ##
// ##
// N O N I N L I N E F U N C T I O N S ##
// ##
// ##
//############################################################################
//
// initialization of the thread_local pointer to the auxiliary buffer
template < uint32_t Block_size, class Iter_t, class Compare >
thread_local typename std::iterator_traits< Iter_t >
::value_type *backbone< Block_size, Iter_t, Compare >::buf = nullptr;
//------------------------------------------------------------------------
// function : backbone
/// @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
//------------------------------------------------------------------------
template < uint32_t Block_size, class Iter_t, class Compare >
backbone< Block_size, Iter_t, Compare >
::backbone (Iter_t first, Iter_t last, Compare comp)
: global_range (first, last), cmp (comp), error (false)
{
assert ((last - first) >= 0);
if (first == last) return; // nothing to do
nelem = size_t (last - first);
nblock = (nelem + Block_size - 1) / Block_size;
ntail = (nelem % Block_size);
index.reserve (nblock + 1);
for (size_t i = 0; i < nblock; ++i) index.emplace_back (block_pos (i));
range_tail.first =
(ntail == 0) ? last : (first + ((nblock - 1) * Block_size));
range_tail.last = last;
};
//
//-------------------------------------------------------------------------
// function : exec
/// @brief execute the function_t stored in works, until counter is zero
//
/// @param counter : atomic counter. When 0 exits the function
//-------------------------------------------------------------------------
template < uint32_t Block_size, class Iter_t, class Compare >
void backbone< Block_size, Iter_t, Compare >::exec (atomic_t &counter)
{
function_t func_exec;
while (bscu::atomic_read (counter) != 0)
{
if (works.pop_move_back (func_exec)) func_exec ( );
else std::this_thread::yield ( );
};
};
//
//****************************************************************************
}; // End namespace blk_detail
}; // End namespace sort
}; // End namespace boost
//****************************************************************************
#endif
|
