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
19namespace 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