// Copyright David Abrahams 2006. Distributed under the Boost
// Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#include <boost/noncopyable.hpp>
#include <boost/thread.hpp>
#include <boost/bind.hpp>
#include <iostream>
#include <ostream>

namespace {
boost::mutex io_mutex;

struct synco
{
    synco(std::ostream& os = std::cout) : os(os), lock(io_mutex) {}
    
    template <class T>
    std::ostream& operator<<(T const& x)
    {
        return os << x;
    }
    std::ostream& os;
    boost::mutex::scoped_lock lock;
};
    
} // namespace

// Lock a couple of Mutexes in order to prevent deadlocks
template <class Mutex>
struct lockpair
{
    lockpair(Mutex& m1, Mutex& m2)
      : l1(std::less<Mutex*>()(&m1,&m2) ? m1 : m2),
        l2(std::less<Mutex*>()(&m1,&m2) ? m2 : m1)
    {}
    
    typename Mutex::scoped_lock l1, l2;
};

class collab : boost::noncopyable
{
 public:
    collab() : partner(0) {}
    ~collab() { this->decouple(); }

    typedef boost::mutex mutex;
    
    void couple(collab* new_partner)
    {
        if (new_partner == this)
            return;
        
        while (1)
        {
            this->decouple();
            new_partner->decouple();

            lockpair<mutex> lk(this->gate, new_partner->gate);
            if (this->partner == 0 && new_partner->partner == 0)
            {
                synco() << "partnered " << this << " with " << new_partner << std::endl;
                this->partner = new_partner;
                new_partner->partner = this;
                return;
            }
        }
    }
    
    void decouple()
    {
        while (1)
        {
            // First get ahold of our current partner, if any
            collab* current_partner;
            {
                mutex::scoped_lock lk(this->gate);
                current_partner = this->partner;
                if (!current_partner)
                    return;  // already decoupled
                
                // We must release our lock so that we can re-lock in order
            }

            // Ordered locking to prevent deadlock
            lockpair<mutex> lk(this->gate, current_partner->gate);

            // We may have been decoupled while unlocked
            if (!this->partner)
                return;

            // If we still have the same partner, we can now decouple
            // both collaborators
            if (current_partner == this->partner)
            {
                synco() << "soloing " << this << std::endl;
                current_partner->partner = 0;
                this->partner = 0;
                return;
            }
            
            // Otherwise, release all locks and try again
            synco() << "partner changed on " << this << " from " << current_partner << " to " << this->partner << std::endl;
        }
    }

 private:
    collab* partner;
    mutex gate;
};

collab c[4];

void test()
{
    for (int i = 0; i < 400; ++i)
    {
        int n = std::rand() % 4;
        int m = std::rand() % 5 - 1;
        if (m < 0)
            c[n].decouple();
        else
            c[n].couple(&c[m]);
    }
}
int main()
{
    boost::thread_group t;
    for (int i = 0; i < 4; ++i)
        t.create_thread(test);
    t.join_all();
    return 0;
}