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