boost/thread/lock_algorithms.hpp

   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