Try-lock semaphore using standard libraries

Question

I'm building a Sokoban solver. Since I'm doing depth-first search (yes, it is a horrible idea, I know) I wish to do it multithreaded.

My function is recursive. I would therefore like a semaphore (like what is suggested here), but I need to be able to attempt a lock, and in case of no lock-ability then just proceed as if nothing happened.

The semaphores are supposed to control whether or not a new thread should be initiated. Since I am using a recursive function I can imagine a whole lot of overhead, were I to just implement the linked semaphore and wait for a release.

SO: How to try to lock a semaphore, but skip waiting if no more semaphores are available? Or is there a better solution than semaphores?

My build chain supports C++14. I have Boost installed, but I would like to avoid third party libraries. I am using Ubuntu 14.04.

(When I have done what I want with this, I'll have a go at IDA*, so just focus on what I want to achieve rather than solving the underlying but enormous problem with my approach to solving a Sokoban puzzle :-) )

Answer 1

So you have to add a new method to semaphore class (try)

// Boost is needed no more
#include <condition_variable>
#include <mutex>

using namespace std;

class semaphore
{
private:
    mutex mutex_;
    condition_variable condition_;
    unsigned long count_;

public:
    semaphore()
        : count_()
    {}

    void notify()
    {
        unique_lock<mutex> lock(mutex_);
        ++count_;
        condition_.notify_one();
    }

    void wait()
    {
        unique_lock<mutex> lock(mutex_);
        while(!count_)
            condition_.wait(lock);
        --count_;
    }

    bool try()
    {
        unique_lock<mutex> lock(mutex_);

        if (count_)
        {
            --count_;
            return true;
        }
        else
        {
            return false;
        }
    }
};