Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: // (C) Copyright 2007 Anthony Williams
Chris@16: // (C) Copyright 2011-2012 Vicente J. Botet Escriba
Chris@16: 
Chris@16: #ifndef BOOST_THREAD_LOCK_ALGORITHMS_HPP
Chris@16: #define BOOST_THREAD_LOCK_ALGORITHMS_HPP
Chris@16: 
Chris@16: #include <boost/thread/detail/config.hpp>
Chris@16: #include <boost/thread/lock_types.hpp>
Chris@16: #include <boost/thread/lockable_traits.hpp>
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <iterator>
Chris@16: 
Chris@16: #include <boost/config/abi_prefix.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:   namespace detail
Chris@16:   {
Chris@16:     template <typename MutexType1, typename MutexType2>
Chris@16:     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
Chris@16:       if (!l1)
Chris@16:       {
Chris@16:         return 1;
Chris@16:       }
Chris@16:       if (!m2.try_lock())
Chris@16:       {
Chris@16:         return 2;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2, typename MutexType3>
Chris@16:     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
Chris@16:       if (!l1)
Chris@16:       {
Chris@16:         return 1;
Chris@16:       }
Chris@16:       if (unsigned const failed_lock=try_lock_internal(m2,m3))
Chris@16:       {
Chris@16:         return failed_lock + 1;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
Chris@16:     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
Chris@16:       if (!l1)
Chris@16:       {
Chris@16:         return 1;
Chris@16:       }
Chris@16:       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4))
Chris@16:       {
Chris@16:         return failed_lock + 1;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
Chris@16:     unsigned try_lock_internal(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1, boost::try_to_lock);
Chris@16:       if (!l1)
Chris@16:       {
Chris@16:         return 1;
Chris@16:       }
Chris@16:       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4,m5))
Chris@16:       {
Chris@16:         return failed_lock + 1;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2>
Chris@16:     unsigned lock_helper(MutexType1& m1, MutexType2& m2)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1);
Chris@16:       if (!m2.try_lock())
Chris@16:       {
Chris@16:         return 1;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2, typename MutexType3>
Chris@16:     unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1);
Chris@16:       if (unsigned const failed_lock=try_lock_internal(m2,m3))
Chris@16:       {
Chris@16:         return failed_lock;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
Chris@16:     unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1);
Chris@16:       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4))
Chris@16:       {
Chris@16:         return failed_lock;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
Chris@16:     unsigned lock_helper(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
Chris@16:     {
Chris@16:       boost::unique_lock<MutexType1> l1(m1);
Chris@16:       if (unsigned const failed_lock=try_lock_internal(m2,m3,m4,m5))
Chris@16:       {
Chris@16:         return failed_lock;
Chris@16:       }
Chris@16:       l1.release();
Chris@16:       return 0;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail
Chris@16:   {
Chris@16:     template <bool x>
Chris@16:     struct is_mutex_type_wrapper
Chris@16:     {
Chris@16:     };
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2>
Chris@16:     void lock_impl(MutexType1& m1, MutexType2& m2, is_mutex_type_wrapper<true> )
Chris@16:     {
Chris@16:       unsigned const lock_count = 2;
Chris@16:       unsigned lock_first = 0;
Chris@16:       for (;;)
Chris@16:       {
Chris@16:         switch (lock_first)
Chris@16:         {
Chris@16:         case 0:
Chris@16:           lock_first = detail::lock_helper(m1, m2);
Chris@16:           if (!lock_first) return;
Chris@16:           break;
Chris@16:         case 1:
Chris@16:           lock_first = detail::lock_helper(m2, m1);
Chris@16:           if (!lock_first) return;
Chris@16:           lock_first = (lock_first + 1) % lock_count;
Chris@16:           break;
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Iterator>
Chris@16:     void lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   void lock(MutexType1& m1, MutexType2& m2)
Chris@16:   {
Chris@16:     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   void lock(const MutexType1& m1, MutexType2& m2)
Chris@16:   {
Chris@16:     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   void lock(MutexType1& m1, const MutexType2& m2)
Chris@16:   {
Chris@16:     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   void lock(const MutexType1& m1, const MutexType2& m2)
Chris@16:   {
Chris@16:     detail::lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2, typename MutexType3>
Chris@16:   void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3)
Chris@16:   {
Chris@16:     unsigned const lock_count = 3;
Chris@16:     unsigned lock_first = 0;
Chris@16:     for (;;)
Chris@16:     {
Chris@16:       switch (lock_first)
Chris@16:       {
Chris@16:       case 0:
Chris@16:         lock_first = detail::lock_helper(m1, m2, m3);
Chris@16:         if (!lock_first) return;
Chris@16:         break;
Chris@16:       case 1:
Chris@16:         lock_first = detail::lock_helper(m2, m3, m1);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 1) % lock_count;
Chris@16:         break;
Chris@16:       case 2:
Chris@16:         lock_first = detail::lock_helper(m3, m1, m2);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 2) % lock_count;
Chris@16:         break;
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
Chris@16:   void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
Chris@16:   {
Chris@16:     unsigned const lock_count = 4;
Chris@16:     unsigned lock_first = 0;
Chris@16:     for (;;)
Chris@16:     {
Chris@16:       switch (lock_first)
Chris@16:       {
Chris@16:       case 0:
Chris@16:         lock_first = detail::lock_helper(m1, m2, m3, m4);
Chris@16:         if (!lock_first) return;
Chris@16:         break;
Chris@16:       case 1:
Chris@16:         lock_first = detail::lock_helper(m2, m3, m4, m1);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 1) % lock_count;
Chris@16:         break;
Chris@16:       case 2:
Chris@16:         lock_first = detail::lock_helper(m3, m4, m1, m2);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 2) % lock_count;
Chris@16:         break;
Chris@16:       case 3:
Chris@16:         lock_first = detail::lock_helper(m4, m1, m2, m3);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 3) % lock_count;
Chris@16:         break;
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
Chris@16:   void lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
Chris@16:   {
Chris@16:     unsigned const lock_count = 5;
Chris@16:     unsigned lock_first = 0;
Chris@16:     for (;;)
Chris@16:     {
Chris@16:       switch (lock_first)
Chris@16:       {
Chris@16:       case 0:
Chris@16:         lock_first = detail::lock_helper(m1, m2, m3, m4, m5);
Chris@16:         if (!lock_first) return;
Chris@16:         break;
Chris@16:       case 1:
Chris@16:         lock_first = detail::lock_helper(m2, m3, m4, m5, m1);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 1) % lock_count;
Chris@16:         break;
Chris@16:       case 2:
Chris@16:         lock_first = detail::lock_helper(m3, m4, m5, m1, m2);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 2) % lock_count;
Chris@16:         break;
Chris@16:       case 3:
Chris@16:         lock_first = detail::lock_helper(m4, m5, m1, m2, m3);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 3) % lock_count;
Chris@16:         break;
Chris@16:       case 4:
Chris@16:         lock_first = detail::lock_helper(m5, m1, m2, m3, m4);
Chris@16:         if (!lock_first) return;
Chris@16:         lock_first = (lock_first + 4) % lock_count;
Chris@16:         break;
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail
Chris@16:   {
Chris@16:     template <typename Mutex, bool x = is_mutex_type<Mutex>::value>
Chris@16:     struct try_lock_impl_return
Chris@16:     {
Chris@16:       typedef int type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Iterator>
Chris@16:     struct try_lock_impl_return<Iterator, false>
Chris@16:     {
Chris@16:       typedef Iterator type;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename MutexType1, typename MutexType2>
Chris@16:     int try_lock_impl(MutexType1& m1, MutexType2& m2, is_mutex_type_wrapper<true> )
Chris@16:     {
Chris@16:       return ((int) detail::try_lock_internal(m1, m2)) - 1;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Iterator>
Chris@16:     Iterator try_lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> );
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   typename detail::try_lock_impl_return<MutexType1>::type try_lock(MutexType1& m1, MutexType2& m2)
Chris@16:   {
Chris@16:     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   typename detail::try_lock_impl_return<MutexType1>::type try_lock(const MutexType1& m1, MutexType2& m2)
Chris@16:   {
Chris@16:     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   typename detail::try_lock_impl_return<MutexType1>::type try_lock(MutexType1& m1, const MutexType2& m2)
Chris@16:   {
Chris@16:     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2>
Chris@16:   typename detail::try_lock_impl_return<MutexType1>::type try_lock(const MutexType1& m1, const MutexType2& m2)
Chris@16:   {
Chris@16:     return detail::try_lock_impl(m1, m2, detail::is_mutex_type_wrapper<is_mutex_type<MutexType1>::value>());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2, typename MutexType3>
Chris@16:   int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3)
Chris@16:   {
Chris@16:     return ((int) detail::try_lock_internal(m1, m2, m3)) - 1;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4>
Chris@16:   int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4)
Chris@16:   {
Chris@16:     return ((int) detail::try_lock_internal(m1, m2, m3, m4)) - 1;
Chris@16:   }
Chris@16: 
Chris@16:   template <typename MutexType1, typename MutexType2, typename MutexType3, typename MutexType4, typename MutexType5>
Chris@16:   int try_lock(MutexType1& m1, MutexType2& m2, MutexType3& m3, MutexType4& m4, MutexType5& m5)
Chris@16:   {
Chris@16:     return ((int) detail::try_lock_internal(m1, m2, m3, m4, m5)) - 1;
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail
Chris@16:   {
Chris@16:     template <typename Iterator>
Chris@16:     struct range_lock_guard
Chris@16:     {
Chris@16:       Iterator begin;
Chris@16:       Iterator end;
Chris@16: 
Chris@16:       range_lock_guard(Iterator begin_, Iterator end_) :
Chris@16:         begin(begin_), end(end_)
Chris@16:       {
Chris@16:         boost::lock(begin, end);
Chris@16:       }
Chris@16: 
Chris@16:       void release()
Chris@16:       {
Chris@16:         begin = end;
Chris@16:       }
Chris@16: 
Chris@16:       ~range_lock_guard()
Chris@16:       {
Chris@16:         for (; begin != end; ++begin)
Chris@16:         {
Chris@16:           begin->unlock();
Chris@16:         }
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Iterator>
Chris@16:     Iterator try_lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> )
Chris@16: 
Chris@16:     {
Chris@16:       if (begin == end)
Chris@16:       {
Chris@16:         return end;
Chris@16:       }
Chris@16:       typedef typename std::iterator_traits<Iterator>::value_type lock_type;
Chris@16:       unique_lock<lock_type> guard(*begin, try_to_lock);
Chris@16: 
Chris@16:       if (!guard.owns_lock())
Chris@16:       {
Chris@16:         return begin;
Chris@16:       }
Chris@16:       Iterator const failed = boost::try_lock(++begin, end);
Chris@16:       if (failed == end)
Chris@16:       {
Chris@16:         guard.release();
Chris@16:       }
Chris@16: 
Chris@16:       return failed;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   namespace detail
Chris@16:   {
Chris@16:     template <typename Iterator>
Chris@16:     void lock_impl(Iterator begin, Iterator end, is_mutex_type_wrapper<false> )
Chris@16:     {
Chris@16:       typedef typename std::iterator_traits<Iterator>::value_type lock_type;
Chris@16: 
Chris@16:       if (begin == end)
Chris@16:       {
Chris@16:         return;
Chris@16:       }
Chris@16:       bool start_with_begin = true;
Chris@16:       Iterator second = begin;
Chris@16:       ++second;
Chris@16:       Iterator next = second;
Chris@16: 
Chris@16:       for (;;)
Chris@16:       {
Chris@16:         unique_lock<lock_type> begin_lock(*begin, defer_lock);
Chris@16:         if (start_with_begin)
Chris@16:         {
Chris@16:           begin_lock.lock();
Chris@16:           Iterator const failed_lock = boost::try_lock(next, end);
Chris@16:           if (failed_lock == end)
Chris@16:           {
Chris@16:             begin_lock.release();
Chris@16:             return;
Chris@16:           }
Chris@16:           start_with_begin = false;
Chris@16:           next = failed_lock;
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:           detail::range_lock_guard<Iterator> guard(next, end);
Chris@16:           if (begin_lock.try_lock())
Chris@16:           {
Chris@16:             Iterator const failed_lock = boost::try_lock(second, next);
Chris@16:             if (failed_lock == next)
Chris@16:             {
Chris@16:               begin_lock.release();
Chris@16:               guard.release();
Chris@16:               return;
Chris@16:             }
Chris@16:             start_with_begin = false;
Chris@16:             next = failed_lock;
Chris@16:           }
Chris@16:           else
Chris@16:           {
Chris@16:             start_with_begin = true;
Chris@16:             next = second;
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16: }
Chris@16: #include <boost/config/abi_suffix.hpp>
Chris@16: 
Chris@16: #endif