1 //----------------------------------------------------------------------------
2 /// @file scheduler.hpp
3 /// @brief This file contains the implementation of the scheduler for
4 /// dispatch the works stored
5 ///
6 /// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
7 /// Distributed under the Boost Software License, Version 1.0.\n
8 /// ( See accompanyingfile 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_COMMON_SCHEDULER_HPP
15 #define __BOOST_SORT_COMMON_SCHEDULER_HPP
16
17 #include <boost/sort/common/spinlock.hpp>
18 #include <boost/sort/common/search.hpp>
19 #include <boost/sort/common/compare_traits.hpp>
20 #include <scoped_allocator>
21 #include <utility>
22 #include <vector>
23 #include <deque>
24 #include <iostream>
25 #include <unordered_map>
26
27 namespace boost
28 {
29 namespace sort
30 {
31 namespace common
32 {
33
34 //
35 //###########################################################################
36 // ##
37 // ################################################################ ##
38 // # # ##
39 // # C L A S S S C H E D U L E R # ##
40 // # # ##
41 // ################################################################ ##
42 // ##
43 //###########################################################################
44
45 //
46 //---------------------------------------------------------------------------
47 /// @class scheduler
48 /// @brief This class is a concurrent stack controled by a spin_lock
49 /// @remarks
50 //---------------------------------------------------------------------------
51 template<typename Func_t, typename Allocator = std::allocator<Func_t> >
52 struct scheduler
53 {
54 //-----------------------------------------------------------------------
55 // D E F I N I T I O N S
56 //-----------------------------------------------------------------------
57 typedef std::scoped_allocator_adaptor <Allocator> scoped_alloc;
58 typedef std::deque <Func_t, scoped_alloc> deque_t;
59 typedef typename deque_t::iterator it_deque;
60 typedef std::thread::id key_t;
61 typedef std::hash <key_t> hash_t;
62 typedef std::equal_to <key_t> equal_t;
63 typedef std::unique_lock <spinlock_t> lock_t;
64 typedef std::unordered_map <key_t, deque_t, hash_t,
65 equal_t, scoped_alloc> map_t;
66 typedef typename map_t::iterator it_map;
67
68 //-----------------------------------------------------------------------
69 // V A R I A B L E S
70 //-----------------------------------------------------------------------
71 map_t mp;
72 size_t nelem;
73 mutable spinlock_t spl;
74
75 //------------------------------------------------------------------------
76 // function : scheduler
77 /// @brief constructor
78 //------------------------------------------------------------------------
schedulerboost::sort::common::scheduler79 scheduler(void) : mp(), nelem(0) { };
80 //
81 //-----------------------------------------------------------------------
82 // function : scheduler
83 /// @brief Copy & move constructor
84 /// @param [in] VT : stack_cnc from where copy the data
85 //-----------------------------------------------------------------------
86 scheduler(scheduler && VT) = delete;
87 scheduler(const scheduler & VT) = delete;
88 //
89 //------------------------------------------------------------------------
90 // function : ~scheduler
91 /// @brief Destructor
92 //------------------------------------------------------------------------
~schedulerboost::sort::common::scheduler93 virtual ~scheduler(void) {mp.clear();};
94 //
95 //------------------------------------------------------------------------
96 // function : operator =
97 /// @brief Asignation operator
98 /// @param [in] VT : stack_cnc from where copy the data
99 /// @return Reference to the stack_cnc after the copy
100 //------------------------------------------------------------------------
101 scheduler & operator=(const scheduler &VT) = delete;
102 //
103 //------------------------------------------------------------------------
104 // function : size
105 /// @brief Asignation operator
106 /// @param [in] VT : stack_cnc from where copy the data
107 /// @return Reference to the stack_cnc after the copy
108 //------------------------------------------------------------------------
sizeboost::sort::common::scheduler109 size_t size(void) const
110 {
111 lock_t s(spl);
112 return nelem;
113 };
114 //
115 //------------------------------------------------------------------------
116 // function : clear
117 /// @brief Delete all the elements of the stack_cnc.
118 //------------------------------------------------------------------------
clear_allboost::sort::common::scheduler119 void clear_all(void)
120 {
121 lock_t s(spl);
122 mp.clear();
123 nelem = 0;
124 };
125
126 //
127 //------------------------------------------------------------------------
128 // function : insert
129 /// @brief Insert one element in the back of the container
130 /// @param [in] D : value to insert. Can ve a value, a reference or an
131 /// rvalue
132 /// @return iterator to the element inserted
133 /// @remarks This operation is O ( const )
134 //------------------------------------------------------------------------
insertboost::sort::common::scheduler135 void insert(Func_t & f)
136 {
137 lock_t s(spl);
138 key_t th_id = std::this_thread::get_id();
139 it_map itmp = mp.find(th_id);
140 if (itmp == mp.end())
141 {
142 auto aux = mp.emplace(th_id, deque_t());
143 if (aux.second == false) throw std::bad_alloc();
144 itmp = aux.first;
145 };
146 itmp->second.emplace_back(std::move(f));
147 nelem++;
148 };
149
150 //
151 //------------------------------------------------------------------------
152 // function :emplace
153 /// @brief Insert one element in the back of the container
154 /// @param [in] args :group of arguments for to build the object to insert
155 /// @return iterator to the element inserted
156 /// @remarks This operation is O ( const )
157 //------------------------------------------------------------------------
158 template<class ... Args>
emplaceboost::sort::common::scheduler159 void emplace(Args && ... args)
160 {
161 lock_t s(spl);
162 key_t th_id = std::this_thread::get_id();
163 it_map itmp = mp.find(th_id);
164 if (itmp == mp.end())
165 {
166 auto aux = mp.emplace(th_id, deque_t());
167 if (aux.second == false) throw std::bad_alloc();
168 itmp = aux.first;
169 };
170 itmp->second.emplace_back(std::forward <Args>(args) ...);
171 nelem++;
172 };
173 //
174 //------------------------------------------------------------------------
175 // function : insert
176 /// @brief Insert one element in the back of the container
177 /// @param [in] D : value to insert. Can ve a value, a reference or an rvalue
178 /// @return iterator to the element inserted
179 /// @remarks This operation is O ( const )
180 //------------------------------------------------------------------------
181 template<class it_func>
insert_rangeboost::sort::common::scheduler182 void insert_range(it_func first, it_func last)
183 {
184 //--------------------------------------------------------------------
185 // Metaprogramming
186 //--------------------------------------------------------------------
187 typedef value_iter<it_func> value2_t;
188 static_assert (std::is_same< Func_t, value2_t >::value,
189 "Incompatible iterators\n");
190
191 //--------------------------------------------------------------------
192 // Code
193 //--------------------------------------------------------------------
194 assert((last - first) > 0);
195
196 lock_t s(spl);
197 key_t th_id = std::this_thread::get_id();
198 it_map itmp = mp.find(th_id);
199 if (itmp == mp.end())
200 {
201 auto aux = mp.emplace(th_id, deque_t());
202 if (aux.second == true) throw std::bad_alloc();
203 itmp = aux.first;
204 };
205 while (first != last)
206 {
207 itmp->second.emplace_back(std::move(*(first++)));
208 nelem++;
209 };
210 };
211 //
212 //------------------------------------------------------------------------
213 // function : extract
214 /// @brief erase the last element of the tree and return a copy
215 /// @param [out] V : reference to a variable where copy the element
216 /// @return code of the operation
217 /// 0- Element erased
218 /// 1 - Empty tree
219 /// @remarks This operation is O(1)
220 //------------------------------------------------------------------------
extractboost::sort::common::scheduler221 bool extract(Func_t & f)
222 {
223 lock_t s(spl);
224 if (nelem == 0) return false;
225 key_t th_id = std::this_thread::get_id();
226 it_map itmp = mp.find(th_id);
227 if (itmp != mp.end() and not itmp->second.empty())
228 {
229 f = std::move(itmp->second.back());
230 itmp->second.pop_back();
231 --nelem;
232 return true;
233 };
234 for (itmp = mp.begin(); itmp != mp.end(); ++itmp)
235 {
236 if (itmp->second.empty()) continue;
237 f = std::move(itmp->second.back());
238 itmp->second.pop_back();
239 --nelem;
240 return true;
241 }
242 return false;
243 };
244 };
245 // end class scheduler
246 //*************************************************************************
247 // P R I N T F U N C T I O N S
248 //************************************************************************
249 template<class ... Args>
operator <<(std::ostream & out,const std::deque<Args...> & dq)250 std::ostream & operator <<(std::ostream &out, const std::deque<Args ...> & dq)
251 {
252 for (uint32_t i = 0; i < dq.size(); ++i)
253 out << dq[i] << " ";
254 out << std::endl;
255 return out;
256 }
257
258 template<typename Func_t, typename Allocator = std::allocator<Func_t> >
operator <<(std::ostream & out,const scheduler<Func_t,Allocator> & sch)259 std::ostream & operator <<(std::ostream &out,
260 const scheduler<Func_t, Allocator> &sch)
261 {
262 std::unique_lock < spinlock_t > s(sch.spl);
263 out << "Nelem :" << sch.nelem << std::endl;
264 for (auto it = sch.mp.begin(); it != sch.mp.end(); ++it)
265 {
266 out << it->first << " :" << it->second << std::endl;
267 }
268 return out;
269 }
270
271 //***************************************************************************
272 };// end namespace common
273 };// end namespace sort
274 };// end namespace boost
275 //***************************************************************************
276 #endif
277