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> try_lock_internal(MutexType1 & m1,MutexType2 & m2)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> try_lock_internal(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3)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> try_lock_internal(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4)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> try_lock_internal(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4,MutexType5 & m5)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> lock_helper(MutexType1 & m1,MutexType2 & m2)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> lock_helper(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3)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> lock_helper(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4)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> lock_helper(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4,MutexType5 & m5)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> lock_impl(MutexType1 & m1,MutexType2 & m2,is_mutex_type_wrapper<true>)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> lock(MutexType1 & m1,MutexType2 & m2)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> lock(const MutexType1 & m1,MutexType2 & m2)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> lock(MutexType1 & m1,const MutexType2 & m2)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> lock(const MutexType1 & m1,const MutexType2 & m2)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> lock(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3)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> lock(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4)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> lock(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4,MutexType5 & m5)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> try_lock_impl(MutexType1 & m1,MutexType2 & m2,is_mutex_type_wrapper<true>)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> try_lock(MutexType1 & m1,MutexType2 & m2)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> try_lock(const MutexType1 & m1,MutexType2 & m2)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> try_lock(MutexType1 & m1,const MutexType2 & m2)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> try_lock(const MutexType1 & m1,const MutexType2 & m2)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> try_lock(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3)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> try_lock(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4)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> try_lock(MutexType1 & m1,MutexType2 & m2,MutexType3 & m3,MutexType4 & m4,MutexType5 & m5)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 range_lock_guardboost::detail::range_lock_guard363 range_lock_guard(Iterator begin_, Iterator end_) : 364 begin(begin_), end(end_) 365 { 366 boost::lock(begin, end); 367 } 368 releaseboost::detail::range_lock_guard369 void release() 370 { 371 begin = end; 372 } 373 ~range_lock_guardboost::detail::range_lock_guard374 ~range_lock_guard() 375 { 376 for (; begin != end; ++begin) 377 { 378 begin->unlock(); 379 } 380 } 381 }; 382 383 template <typename Iterator> try_lock_impl(Iterator begin,Iterator end,is_mutex_type_wrapper<false>)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> lock_impl(Iterator begin,Iterator end,is_mutex_type_wrapper<false>)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