run-jobs.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Christian Schulte, 2017
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */


namespace Gecode { namespace Support {

  template<class RetType>
  class Job {
  public:
    virtual RetType run(int i) = 0;
    virtual ~Job(void) {}
  };

  template<class RetType>
  class JobStop {
  protected:
    RetType r;
  public:
    JobStop(RetType r0);
    RetType result(void) const;
  };

  template<class Jobs, class RetType>
  class RunJobs {
  protected:
    class Master;
    class Worker : public Runnable {
    protected:
      Job<RetType>* job;
      Master* master;
      int idx;
    public:
      Worker(Job<RetType>* j, Master* m, int i);
      virtual void run(void);
      virtual ~Worker(void);
    };
    class Master {
    protected:
      Mutex m;
      Event e;
      unsigned int n_threads;
      Jobs& jobs;
      int idx;
      RetType sres; 
      int sidx;
      DynamicQueue<RetType,Heap> rs;
    public:
      Job<RetType>* next(int& i);
      void report(RetType r);
      void stop(RetType r, int i);
      bool done(void) const;
      Master(Jobs& j, unsigned int m);
      bool run(RetType& r);
      bool stopped(void) const;
      int stoppedjob(RetType& r) const;
      bool needthread(void);
      ~Master(void);
    };
    class Deleter : public Runnable {
    protected:
      Master* master;
    public:
      Deleter(Master* m);
      virtual void run(void);
    };
    Master* master;
  public:
    RunJobs(Jobs& j, unsigned int m);
    bool run(RetType& r);
    bool stopped(int& i, RetType& r) const;
    ~RunJobs(void);
  };



  template<class RetType>
  forceinline
  JobStop<RetType>::JobStop(RetType r0) : r(r0) {}

  template<class RetType>
  forceinline RetType
  JobStop<RetType>::result(void) const {
    return r;
  }



  template<class Jobs, class RetType>
  forceinline
  RunJobs<Jobs,RetType>::Worker::Worker(Job<RetType>* j, 
                                        Master* m,
                                        int i) 
    : Runnable(true), job(j), master(m), idx(i) {}
  
  template<class Jobs, class RetType>
  RunJobs<Jobs,RetType>::Worker::~Worker(void) {}


  template<class Jobs, class RetType>
  inline int
  RunJobs<Jobs,RetType>::Master::stoppedjob(RetType& r) const {
    r = sres;
    return sidx;
  }

  template<class Jobs, class RetType>
  inline bool
  RunJobs<Jobs,RetType>::Master::stopped(void) const {
    return sidx >= 0;
  }

  template<class Jobs, class RetType>
  forceinline Job<RetType>*
  RunJobs<Jobs,RetType>::Master::next(int& i) {
    m.acquire();
    Job<RetType>* j;
    if (jobs() && !stopped()) {
      j = jobs.job(); i=idx++;
    } else {
      j = NULL;
      n_threads--;
      e.signal();
    }
    m.release();
    return j;
  }

  template<class Jobs, class RetType>
  forceinline void
  RunJobs<Jobs,RetType>::Master::report(RetType r) {
    m.acquire();
    rs.push(r); 
    e.signal();
    m.release();
  }

  template<class Jobs, class RetType>
  forceinline void
  RunJobs<Jobs,RetType>::Master::stop(RetType r, int i) {
    m.acquire();
    if (!stopped()) {
      sres=r; sidx = i;
    }
    rs.push(r); 
    e.signal();
    m.release();
  }

  template<class Jobs, class RetType>
  void
  RunJobs<Jobs,RetType>::Worker::run(void) {
    do {
      try {
        RetType r = job->run(idx);
        master->report(r);
      } catch (JobStop<RetType>& js) {
        master->stop(js.result(),idx);
      }
      delete job;
      job = master->next(idx);
    } while (job != NULL);
  }

  template<class Jobs, class RetType>
  forceinline bool
  RunJobs<Jobs,RetType>::Master::done(void) const {
    return (n_threads == 0) && (!jobs() || stopped()) && rs.empty();
  }

  template<class Jobs, class RetType>
  inline
  RunJobs<Jobs,RetType>::Master::Master(Jobs& j, unsigned int m_threads) 
    : n_threads(0), jobs(j), idx(0), sidx(-1), rs(heap) {
    m.acquire();
    while ((n_threads < m_threads) && jobs()) {
      if (stopped())
        break;
      Thread::run(new Worker(jobs.job(),this,idx));
      n_threads++; idx++;
    }
    m.release();
  }

  template<class Jobs, class RetType>
  inline bool
  RunJobs<Jobs,RetType>::Master::run(RetType& r) {
    m.acquire();
    if (done()) {
      m.release();
      return false;
    }
    if (!rs.empty()) {
      r = rs.pop();
      m.release();
      return true;
    }
    m.release();
    while (true) {
      e.wait();
      m.acquire();
      if (done()) {
        m.release();
        return false;
      }
      if (!rs.empty()) {
        r = rs.pop();
        m.release();
        return true;
      }
      m.release();
    }
    GECODE_NEVER;
  }

  template<class Jobs, class RetType>
  inline bool
  RunJobs<Jobs,RetType>::Master::needthread(void) {
    bool n;
    m.acquire();
    while (!rs.empty())
      rs.pop().~RetType();
    sidx = 0;
    n = !done();
    m.release();
    return n;
  }

  template<class Jobs, class RetType>
  inline
  RunJobs<Jobs,RetType>::Master::~Master(void) {
    sidx = 0;
    RetType r;
    while (run(r))
      r.~RetType();
  }

  template<class Jobs, class RetType>
  forceinline
  RunJobs<Jobs,RetType>::Deleter::Deleter(Master* m) 
    : Runnable(true), master(m) {}

  template<class Jobs, class RetType>
  void
  RunJobs<Jobs,RetType>::Deleter::run(void) {
    delete master;
  }





  template<class Jobs, class RetType>
  inline bool
  RunJobs<Jobs,RetType>::stopped(int& i, RetType& r) const {
    i = master->stoppedjob(r);
    return i >= 0;
  }

  template<class Jobs, class RetType>
  inline
  RunJobs<Jobs,RetType>::RunJobs(Jobs& j, unsigned int m) 
    : master(new Master(j,m)) {}

  template<class Jobs, class RetType>
  inline bool
  RunJobs<Jobs,RetType>::run(RetType& r) {
    return master->run(r);
  }

  template<class Jobs, class RetType>
  inline
  RunJobs<Jobs,RetType>::~RunJobs(void) {
    if (!master->needthread())
      delete master;
    else
      Thread::run(new Deleter(master));
  }


}}

// STATISTICS: support-any