boost/thread/lock_algorithms.hpp

0001 // Distributed under the Boost Software License, Version 1.0. (See
0002 // accompanying file LICENSE_1_0.txt or copy at
0003 // http://www.boost.org/LICENSE_1_0.txt)
0004 // (C) Copyright 2007 Anthony Williams
0005 // (C) Copyright 2011-2012 Vicente J. Botet Escriba
0006
0007 #ifndef BOOST_THREAD_LOCK_ALGORITHMS_HPP
0008 #define BOOST_THREAD_LOCK_ALGORITHMS_HPP
0009
0010 #include <boost/thread/detail/config.hpp>
0011 #include <boost/thread/lock_types.hpp>
0012 #include <boost/thread/lockable_traits.hpp>
0013
0014 #include <algorithm>
0015 #include <iterator>
0016
0017 #include <boost/config/abi_prefix.hpp>
0018
0019 namespace boost
0020 {
0021   namespace detail
0022   {
0023     template <typename MutexType1, typename MutexType2>
0024     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2)
0025     {
0026       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
0027       if (!l1)
0028       {
0029         return 1;
0030       }
0031       if (!m2.try_lock())
0032       {
0033         return 2;
0034       }
0035       l1.release();
0036       return 0;
0037     }
0038
0039     template <typename MutexType1, typename MutexType2, typename MutexType3>
0040     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3)
0041     {
0042       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
0043       if (!l1)
0044       {
0045         return 1;
0046       }
0047       if (unsigned const failed_lock=try_lock_internal(m2,m3))
0048       {
0049         return failed_lock + 1;
0050       }
0051       l1.release();
0052       return 0;
0053     }
0054
0055     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
0056     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
0057     {
0058       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
0059       if (!l1)
0060       {
0061         return 1;
0062       }
0063       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4))
0064       {
0065         return failed_lock + 1;
0066       }
0067       l1.release();
0068       return 0;
0069     }
0070
0071     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
0072     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
0073     {
0074       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
0075       if (!l1)
0076       {
0077         return 1;
0078       }
0079       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4,m5))
0080       {
0081         return failed_lock + 1;
0082       }
0083       l1.release();
0084       return 0;
0085     }
0086
0087     template <typename MutexType1, typename MutexType2>
0088     unsigned lock_helper(MutexType1& m1, MutexType2& m2)
0089     {
0090       boost::unique_lock<MutexType1> l1(m1);
0091       if (!m2.try_lock())
0092       {
0093         return 1;
0094       }
0095       l1.release();
0096       return 0;
0097     }
0098
0099     template <typename MutexType1, typename MutexType2, typename MutexType3>
0100     unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3)
0101     {
0102       boost::unique_lock<MutexType1> l1(m1);
0103       if (unsigned const failed_lock=try_lock_internal(m2,m3))
0104       {
0105         return failed_lock;
0106       }
0107       l1.release();
0108       return 0;
0109     }
0110
0111     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
0112     unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
0113     {
0114       boost::unique_lock<MutexType1> l1(m1);
0115       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4))
0116       {
0117         return failed_lock;
0118       }
0119       l1.release();
0120       return 0;
0121     }
0122
0123     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
0124     unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
0125     {
0126       boost::unique_lock<MutexType1> l1(m1);
0127       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4,m5))
0128       {
0129         return failed_lock;
0130       }
0131       l1.release();
0132       return 0;
0133     }
0134   }
0135
0136   namespace detail
0137   {
0138     template <bool x>
0139     struct is_mutex_type_wrapper
0140     {
0141     };
0142
0143     template <typename MutexType1, typename MutexType2>
0144     void lock_impl(MutexType1& m1, MutexType2& m2, is_mutex_type_wrapper<true> )
0145     {
0146       unsigned const lock_count = 2;
0147       unsigned lock_first = 0;
0148       for (;;)
0149       {
0150         switch (lock_first)
0151         {
0152         case 0:
0153           lock_first = detail::lock_helper(m1, m2);
0154           if (!lock_first) return;
0155           break;
0156         case 1:
0157           lock_first = detail::lock_helper(m2, m1);
0158           if (!lock_first) return;
0159           lock_first = (lock_first + 1) % lock_count;
0160           break;
0161         }
0162       }
0163     }
0164
0165     template <typename Iterator>
0166     void lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> );
0167   }
0168
0169   template <typename MutexType1, typename MutexType2>
0170   void lock(MutexType1& m1, MutexType2& m2)
0171   {
0172     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0173   }
0174
0175   template <typename MutexType1, typename MutexType2>
0176   void lock(const MutexType1& m1, MutexType2& m2)
0177   {
0178     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0179   }
0180
0181   template <typename MutexType1, typename MutexType2>
0182   void lock(MutexType1& m1, const MutexType2& m2)
0183   {
0184     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0185   }
0186
0187   template <typename MutexType1, typename MutexType2>
0188   void lock(const MutexType1& m1, const MutexType2& m2)
0189   {
0190     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0191   }
0192
0193   template <typename MutexType1, typename MutexType2, typename MutexType3>
0194   void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3)
0195   {
0196     unsigned const lock_count = 3;
0197     unsigned lock_first = 0;
0198     for (;;)
0199     {
0200       switch (lock_first)
0201       {
0202       case 0:
0203         lock_first = detail::lock_helper(m1, m2, m3);
0204         if (!lock_first) return;
0205         break;
0206       case 1:
0207         lock_first = detail::lock_helper(m2, m3, m1);
0208         if (!lock_first) return;
0209         lock_first = (lock_first + 1) % lock_count;
0210         break;
0211       case 2:
0212         lock_first = detail::lock_helper(m3, m1, m2);
0213         if (!lock_first) return;
0214         lock_first = (lock_first + 2) % lock_count;
0215         break;
0216       }
0217     }
0218   }
0219
0220   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
0221   void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
0222   {
0223     unsigned const lock_count = 4;
0224     unsigned lock_first = 0;
0225     for (;;)
0226     {
0227       switch (lock_first)
0228       {
0229       case 0:
0230         lock_first = detail::lock_helper(m1, m2, m3, m4);
0231         if (!lock_first) return;
0232         break;
0233       case 1:
0234         lock_first = detail::lock_helper(m2, m3, m4, m1);
0235         if (!lock_first) return;
0236         lock_first = (lock_first + 1) % lock_count;
0237         break;
0238       case 2:
0239         lock_first = detail::lock_helper(m3, m4, m1, m2);
0240         if (!lock_first) return;
0241         lock_first = (lock_first + 2) % lock_count;
0242         break;
0243       case 3:
0244         lock_first = detail::lock_helper(m4, m1, m2, m3);
0245         if (!lock_first) return;
0246         lock_first = (lock_first + 3) % lock_count;
0247         break;
0248       }
0249     }
0250   }
0251
0252   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
0253   void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
0254   {
0255     unsigned const lock_count = 5;
0256     unsigned lock_first = 0;
0257     for (;;)
0258     {
0259       switch (lock_first)
0260       {
0261       case 0:
0262         lock_first = detail::lock_helper(m1, m2, m3, m4, m5);
0263         if (!lock_first) return;
0264         break;
0265       case 1:
0266         lock_first = detail::lock_helper(m2, m3, m4, m5, m1);
0267         if (!lock_first) return;
0268         lock_first = (lock_first + 1) % lock_count;
0269         break;
0270       case 2:
0271         lock_first = detail::lock_helper(m3, m4, m5, m1, m2);
0272         if (!lock_first) return;
0273         lock_first = (lock_first + 2) % lock_count;
0274         break;
0275       case 3:
0276         lock_first = detail::lock_helper(m4, m5, m1, m2, m3);
0277         if (!lock_first) return;
0278         lock_first = (lock_first + 3) % lock_count;
0279         break;
0280       case 4:
0281         lock_first = detail::lock_helper(m5, m1, m2, m3, m4);
0282         if (!lock_first) return;
0283         lock_first = (lock_first + 4) % lock_count;
0284         break;
0285       }
0286     }
0287   }
0288
0289   namespace detail
0290   {
0291     template <typename Mutex, bool x = is_mutex_type<Mutex>::value>
0292     struct try_lock_impl_return
0293     {
0294       typedef int type;
0295     };
0296
0297     template <typename Iterator>
0298     struct try_lock_impl_return<Iterator, false>
0299     {
0300       typedef Iterator type;
0301     };
0302
0303     template <typename MutexType1, typename MutexType2>
0304     int try_lock_impl(MutexType1& m1, MutexType2& m2, is_mutex_type_wrapper<true> )
0305     {
0306       return ((int) detail::try_lock_internal(m1, m2)) - 1;
0307     }
0308
0309     template <typename Iterator>
0310     Iterator try_lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> );
0311   }
0312
0313   template <typename MutexType1, typename MutexType2>
0314   typename detail::try_lock_impl_return<MutexType1>::type try_lock(MutexType1& m1, MutexType2& m2)
0315   {
0316     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0317   }
0318
0319   template <typename MutexType1, typename MutexType2>
0320   typename detail::try_lock_impl_return<MutexType1>::type try_lock(const MutexType1& m1, MutexType2& m2)
0321   {
0322     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0323   }
0324
0325   template <typename MutexType1, typename MutexType2>
0326   typename detail::try_lock_impl_return<MutexType1>::type try_lock(MutexType1& m1, const MutexType2& m2)
0327   {
0328     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0329   }
0330
0331   template <typename MutexType1, typename MutexType2>
0332   typename detail::try_lock_impl_return<MutexType1>::type try_lock(const MutexType1& m1, const MutexType2& m2)
0333   {
0334     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
0335   }
0336
0337   template <typename MutexType1, typename MutexType2, typename MutexType3>
0338   int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3)
0339   {
0340     return ((int) detail::try_lock_internal(m1, m2, m3)) - 1;
0341   }
0342
0343   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
0344   int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
0345   {
0346     return ((int) detail::try_lock_internal(m1, m2, m3, m4)) - 1;
0347   }
0348
0349   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
0350   int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
0351   {
0352     return ((int) detail::try_lock_internal(m1, m2, m3, m4, m5)) - 1;
0353   }
0354
0355   namespace detail
0356   {
0357     template <typename Iterator>
0358     struct range_lock_guard
0359     {
0360       Iterator begin;
0361       Iterator end;
0362
0363       range_lock_guard(Iterator begin_, Iterator end_) :
0364         begin(begin_), end(end_)
0365       {
0366         boost::lock(begin, end);
0367       }
0368
0369       void release()
0370       {
0371         begin = end;
0372       }
0373
0374       ~range_lock_guard()
0375       {
0376         for (; begin != end; ++begin)
0377         {
0378           begin->unlock();
0379         }
0380       }
0381     };
0382
0383     template <typename Iterator>
0384     Iterator try_lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> )
0385
0386     {
0387       if (begin == end)
0388       {
0389         return end;
0390       }
0391       typedef typename std::iterator_traits<Iterator>::value_type lock_type;
0392       unique_lock<lock_type> guard(*begin, try_to_lock);
0393
0394       if (!guard.owns_lock())
0395       {
0396         return begin;
0397       }
0398       Iterator const failed = boost::try_lock(++begin, end);
0399       if (failed == end)
0400       {
0401         guard.release();
0402       }
0403
0404       return failed;
0405     }
0406   }
0407
0408   namespace detail
0409   {
0410     template <typename Iterator>
0411     void lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> )
0412     {
0413       typedef typename std::iterator_traits<Iterator>::value_type lock_type;
0414
0415       if (begin == end)
0416       {
0417         return;
0418       }
0419       bool start_with_begin = true;
0420       Iterator second = begin;
0421       ++second;
0422       Iterator next = second;
0423
0424       for (;;)
0425       {
0426         unique_lock<lock_type> begin_lock(*begin, defer_lock);
0427         if (start_with_begin)
0428         {
0429           begin_lock.lock();
0430           Iterator const failed_lock = boost::try_lock(next, end);
0431           if (failed_lock == end)
0432           {
0433             begin_lock.release();
0434             return;
0435           }
0436           start_with_begin = false;
0437           next = failed_lock;
0438         }
0439         else
0440         {
0441           detail::range_lock_guard<Iterator> guard(next, end);
0442           if (begin_lock.try_lock())
0443           {
0444             Iterator const failed_lock = boost::try_lock(second, next);
0445             if (failed_lock == next)
0446             {
0447               begin_lock.release();
0448               guard.release();
0449               return;
0450             }
0451             start_with_begin = false;
0452             next = failed_lock;
0453           }
0454           else
0455           {
0456             start_with_begin = true;
0457             next = second;
0458           }
0459         }
0460       }
0461     }
0462
0463   }
0464
0465 }
0466 #include <boost/config/abi_suffix.hpp>
0467
0468 #endif