1 | // Distributed under the Boost Software License, Version 1.0. (See |
2 | // accompanying file LICENSE_1_0.txt or copy at |
3 | // http://www.boost.org/LICENSE_1_0.txt) |
4 | // (C) Copyright 2007 Anthony Williams |
5 | // (C) Copyright 2011-2012 Vicente J. Botet Escriba |
6 | |
7 | #ifndef BOOST_THREAD_LOCK_ALGORITHMS_HPP |
8 | #define BOOST_THREAD_LOCK_ALGORITHMS_HPP |
9 | |
10 | #include <boost/thread/detail/config.hpp> |
11 | #include <boost/thread/lock_types.hpp> |
12 | #include <boost/thread/lockable_traits.hpp> |
13 | |
14 | #include <algorithm> |
15 | #include <iterator> |
16 | |
17 | #include <boost/config/abi_prefix.hpp> |
18 | |
19 | namespace boost |
20 | { |
21 | namespace detail |
22 | { |
23 | template <typename MutexType1, typename MutexType2> |
24 | unsigned try_lock_internal(MutexType1& m1, MutexType2& m2) |
25 | { |
26 | boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock); |
27 | if (!l1) |
28 | { |
29 | return 1; |
30 | } |
31 | if (!m2.try_lock()) |
32 | { |
33 | return 2; |
34 | } |
35 | l1.release(); |
36 | return 0; |
37 | } |
38 | |
39 | template <typename MutexType1, typename MutexType2, typename MutexType3> |
40 | unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3) |
41 | { |
42 | boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock); |
43 | if (!l1) |
44 | { |
45 | return 1; |
46 | } |
47 | if (unsigned const failed_lock=try_lock_internal(m2,m3)) |
48 | { |
49 | return failed_lock + 1; |
50 | } |
51 | l1.release(); |
52 | return 0; |
53 | } |
54 | |
55 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4> |
56 | unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4) |
57 | { |
58 | boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock); |
59 | if (!l1) |
60 | { |
61 | return 1; |
62 | } |
63 | if (unsigned const failed_lock=try_lock_internal(m2,m3,m4)) |
64 | { |
65 | return failed_lock + 1; |
66 | } |
67 | l1.release(); |
68 | return 0; |
69 | } |
70 | |
71 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5> |
72 | unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5) |
73 | { |
74 | boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock); |
75 | if (!l1) |
76 | { |
77 | return 1; |
78 | } |
79 | if (unsigned const failed_lock=try_lock_internal(m2,m3,m4,m5)) |
80 | { |
81 | return failed_lock + 1; |
82 | } |
83 | l1.release(); |
84 | return 0; |
85 | } |
86 | |
87 | template <typename MutexType1, typename MutexType2> |
88 | unsigned lock_helper(MutexType1& m1, MutexType2& m2) |
89 | { |
90 | boost::unique_lock<MutexType1> l1(m1); |
91 | if (!m2.try_lock()) |
92 | { |
93 | return 1; |
94 | } |
95 | l1.release(); |
96 | return 0; |
97 | } |
98 | |
99 | template <typename MutexType1, typename MutexType2, typename MutexType3> |
100 | unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3) |
101 | { |
102 | boost::unique_lock<MutexType1> l1(m1); |
103 | if (unsigned const failed_lock=try_lock_internal(m2,m3)) |
104 | { |
105 | return failed_lock; |
106 | } |
107 | l1.release(); |
108 | return 0; |
109 | } |
110 | |
111 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4> |
112 | unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4) |
113 | { |
114 | boost::unique_lock<MutexType1> l1(m1); |
115 | if (unsigned const failed_lock=try_lock_internal(m2,m3,m4)) |
116 | { |
117 | return failed_lock; |
118 | } |
119 | l1.release(); |
120 | return 0; |
121 | } |
122 | |
123 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5> |
124 | unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5) |
125 | { |
126 | boost::unique_lock<MutexType1> l1(m1); |
127 | if (unsigned const failed_lock=try_lock_internal(m2,m3,m4,m5)) |
128 | { |
129 | return failed_lock; |
130 | } |
131 | l1.release(); |
132 | return 0; |
133 | } |
134 | } |
135 | |
136 | namespace detail |
137 | { |
138 | template <bool x> |
139 | struct is_mutex_type_wrapper |
140 | { |
141 | }; |
142 | |
143 | template <typename MutexType1, typename MutexType2> |
144 | void lock_impl(MutexType1& m1, MutexType2& m2, is_mutex_type_wrapper<true> ) |
145 | { |
146 | unsigned const lock_count = 2; |
147 | unsigned lock_first = 0; |
148 | for (;;) |
149 | { |
150 | switch (lock_first) |
151 | { |
152 | case 0: |
153 | lock_first = detail::lock_helper(m1, m2); |
154 | if (!lock_first) return; |
155 | break; |
156 | case 1: |
157 | lock_first = detail::lock_helper(m2, m1); |
158 | if (!lock_first) return; |
159 | lock_first = (lock_first + 1) % lock_count; |
160 | break; |
161 | } |
162 | } |
163 | } |
164 | |
165 | template <typename Iterator> |
166 | void lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> ); |
167 | } |
168 | |
169 | template <typename MutexType1, typename MutexType2> |
170 | void lock(MutexType1& m1, MutexType2& m2) |
171 | { |
172 | detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
173 | } |
174 | |
175 | template <typename MutexType1, typename MutexType2> |
176 | void lock(const MutexType1& m1, MutexType2& m2) |
177 | { |
178 | detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
179 | } |
180 | |
181 | template <typename MutexType1, typename MutexType2> |
182 | void lock(MutexType1& m1, const MutexType2& m2) |
183 | { |
184 | detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
185 | } |
186 | |
187 | template <typename MutexType1, typename MutexType2> |
188 | void lock(const MutexType1& m1, const MutexType2& m2) |
189 | { |
190 | detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
191 | } |
192 | |
193 | template <typename MutexType1, typename MutexType2, typename MutexType3> |
194 | void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3) |
195 | { |
196 | unsigned const lock_count = 3; |
197 | unsigned lock_first = 0; |
198 | for (;;) |
199 | { |
200 | switch (lock_first) |
201 | { |
202 | case 0: |
203 | lock_first = detail::lock_helper(m1, m2, m3); |
204 | if (!lock_first) return; |
205 | break; |
206 | case 1: |
207 | lock_first = detail::lock_helper(m2, m3, m1); |
208 | if (!lock_first) return; |
209 | lock_first = (lock_first + 1) % lock_count; |
210 | break; |
211 | case 2: |
212 | lock_first = detail::lock_helper(m3, m1, m2); |
213 | if (!lock_first) return; |
214 | lock_first = (lock_first + 2) % lock_count; |
215 | break; |
216 | } |
217 | } |
218 | } |
219 | |
220 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4> |
221 | void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4) |
222 | { |
223 | unsigned const lock_count = 4; |
224 | unsigned lock_first = 0; |
225 | for (;;) |
226 | { |
227 | switch (lock_first) |
228 | { |
229 | case 0: |
230 | lock_first = detail::lock_helper(m1, m2, m3, m4); |
231 | if (!lock_first) return; |
232 | break; |
233 | case 1: |
234 | lock_first = detail::lock_helper(m2, m3, m4, m1); |
235 | if (!lock_first) return; |
236 | lock_first = (lock_first + 1) % lock_count; |
237 | break; |
238 | case 2: |
239 | lock_first = detail::lock_helper(m3, m4, m1, m2); |
240 | if (!lock_first) return; |
241 | lock_first = (lock_first + 2) % lock_count; |
242 | break; |
243 | case 3: |
244 | lock_first = detail::lock_helper(m4, m1, m2, m3); |
245 | if (!lock_first) return; |
246 | lock_first = (lock_first + 3) % lock_count; |
247 | break; |
248 | } |
249 | } |
250 | } |
251 | |
252 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5> |
253 | void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5) |
254 | { |
255 | unsigned const lock_count = 5; |
256 | unsigned lock_first = 0; |
257 | for (;;) |
258 | { |
259 | switch (lock_first) |
260 | { |
261 | case 0: |
262 | lock_first = detail::lock_helper(m1, m2, m3, m4, m5); |
263 | if (!lock_first) return; |
264 | break; |
265 | case 1: |
266 | lock_first = detail::lock_helper(m2, m3, m4, m5, m1); |
267 | if (!lock_first) return; |
268 | lock_first = (lock_first + 1) % lock_count; |
269 | break; |
270 | case 2: |
271 | lock_first = detail::lock_helper(m3, m4, m5, m1, m2); |
272 | if (!lock_first) return; |
273 | lock_first = (lock_first + 2) % lock_count; |
274 | break; |
275 | case 3: |
276 | lock_first = detail::lock_helper(m4, m5, m1, m2, m3); |
277 | if (!lock_first) return; |
278 | lock_first = (lock_first + 3) % lock_count; |
279 | break; |
280 | case 4: |
281 | lock_first = detail::lock_helper(m5, m1, m2, m3, m4); |
282 | if (!lock_first) return; |
283 | lock_first = (lock_first + 4) % lock_count; |
284 | break; |
285 | } |
286 | } |
287 | } |
288 | |
289 | namespace detail |
290 | { |
291 | template <typename Mutex, bool x = is_mutex_type<Mutex>::value> |
292 | struct try_lock_impl_return |
293 | { |
294 | typedef int type; |
295 | }; |
296 | |
297 | template <typename Iterator> |
298 | struct try_lock_impl_return<Iterator, false> |
299 | { |
300 | typedef Iterator type; |
301 | }; |
302 | |
303 | template <typename MutexType1, typename MutexType2> |
304 | int try_lock_impl(MutexType1& m1, MutexType2& m2, is_mutex_type_wrapper<true> ) |
305 | { |
306 | return ((int) detail::try_lock_internal(m1, m2)) - 1; |
307 | } |
308 | |
309 | template <typename Iterator> |
310 | Iterator try_lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> ); |
311 | } |
312 | |
313 | template <typename MutexType1, typename MutexType2> |
314 | typename detail::try_lock_impl_return<MutexType1>::type try_lock(MutexType1& m1, MutexType2& m2) |
315 | { |
316 | return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
317 | } |
318 | |
319 | template <typename MutexType1, typename MutexType2> |
320 | typename detail::try_lock_impl_return<MutexType1>::type try_lock(const MutexType1& m1, MutexType2& m2) |
321 | { |
322 | return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
323 | } |
324 | |
325 | template <typename MutexType1, typename MutexType2> |
326 | typename detail::try_lock_impl_return<MutexType1>::type try_lock(MutexType1& m1, const MutexType2& m2) |
327 | { |
328 | return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
329 | } |
330 | |
331 | template <typename MutexType1, typename MutexType2> |
332 | typename detail::try_lock_impl_return<MutexType1>::type try_lock(const MutexType1& m1, const MutexType2& m2) |
333 | { |
334 | return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>()); |
335 | } |
336 | |
337 | template <typename MutexType1, typename MutexType2, typename MutexType3> |
338 | int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3) |
339 | { |
340 | return ((int) detail::try_lock_internal(m1, m2, m3)) - 1; |
341 | } |
342 | |
343 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4> |
344 | int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4) |
345 | { |
346 | return ((int) detail::try_lock_internal(m1, m2, m3, m4)) - 1; |
347 | } |
348 | |
349 | template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5> |
350 | int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5) |
351 | { |
352 | return ((int) detail::try_lock_internal(m1, m2, m3, m4, m5)) - 1; |
353 | } |
354 | |
355 | namespace detail |
356 | { |
357 | template <typename Iterator> |
358 | struct range_lock_guard |
359 | { |
360 | Iterator begin; |
361 | Iterator end; |
362 | |
363 | range_lock_guard(Iterator begin_, Iterator end_) : |
364 | begin(begin_), end(end_) |
365 | { |
366 | boost::lock(begin, end); |
367 | } |
368 | |
369 | void release() |
370 | { |
371 | begin = end; |
372 | } |
373 | |
374 | ~range_lock_guard() |
375 | { |
376 | for (; begin != end; ++begin) |
377 | { |
378 | begin->unlock(); |
379 | } |
380 | } |
381 | }; |
382 | |
383 | template <typename Iterator> |
384 | Iterator try_lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> ) |
385 | |
386 | { |
387 | if (begin == end) |
388 | { |
389 | return end; |
390 | } |
391 | typedef typename std::iterator_traits<Iterator>::value_type lock_type; |
392 | unique_lock<lock_type> guard(*begin, try_to_lock); |
393 | |
394 | if (!guard.owns_lock()) |
395 | { |
396 | return begin; |
397 | } |
398 | Iterator const failed = boost::try_lock(++begin, end); |
399 | if (failed == end) |
400 | { |
401 | guard.release(); |
402 | } |
403 | |
404 | return failed; |
405 | } |
406 | } |
407 | |
408 | namespace detail |
409 | { |
410 | template <typename Iterator> |
411 | void lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> ) |
412 | { |
413 | typedef typename std::iterator_traits<Iterator>::value_type lock_type; |
414 | |
415 | if (begin == end) |
416 | { |
417 | return; |
418 | } |
419 | bool start_with_begin = true; |
420 | Iterator second = begin; |
421 | ++second; |
422 | Iterator next = second; |
423 | |
424 | for (;;) |
425 | { |
426 | unique_lock<lock_type> begin_lock(*begin, defer_lock); |
427 | if (start_with_begin) |
428 | { |
429 | begin_lock.lock(); |
430 | Iterator const failed_lock = boost::try_lock(next, end); |
431 | if (failed_lock == end) |
432 | { |
433 | begin_lock.release(); |
434 | return; |
435 | } |
436 | start_with_begin = false; |
437 | next = failed_lock; |
438 | } |
439 | else |
440 | { |
441 | detail::range_lock_guard<Iterator> guard(next, end); |
442 | if (begin_lock.try_lock()) |
443 | { |
444 | Iterator const failed_lock = boost::try_lock(second, next); |
445 | if (failed_lock == next) |
446 | { |
447 | begin_lock.release(); |
448 | guard.release(); |
449 | return; |
450 | } |
451 | start_with_begin = false; |
452 | next = failed_lock; |
453 | } |
454 | else |
455 | { |
456 | start_with_begin = true; |
457 | next = second; |
458 | } |
459 | } |
460 | } |
461 | } |
462 | |
463 | } |
464 | |
465 | } |
466 | #include <boost/config/abi_suffix.hpp> |
467 | |
468 | #endif |
469 | |