]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |