Line data Source code
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 0 : unsigned lock_helper(MutexType1& m1, MutexType2& m2)
89 : {
90 0 : boost::unique_lock<MutexType1> l1(m1);
91 0 : if (!m2.try_lock())
92 : {
93 : return 1;
94 : }
95 0 : l1.release();
96 0 : 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 0 : void lock(MutexType1& m1, MutexType2& m2)
171 : {
172 0 : 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
|