Quelle runner.hpp Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019 James D. Mitchell
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

// This file contains two classes Runner and Race for competitively running
// different functions/member functions in different threads, and obtaining the
// winner.

#ifndef LIBSEMIGROUPS_RUNNER_HPP_
#define LIBSEMIGROUPS_RUNNER_HPP_

#include <atomic>       // for atomic
#include <chrono>       // for nanoseconds, high_resolution_clock
#include <type_traits>  // for forward

#include "debug.hpp"         // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"     // for LibsemigroupsException
#include "function-ref.hpp"  // for FunctionRef

namespace libsemigroups {
  //! A pseudonym for std::chrono::nanoseconds::max().
  constexpr std::chrono::nanoseconds FOREVER = std::chrono::nanoseconds::max();

  //! Many of the classes in ``libsemigroups`` implementing the algorithms,
  //! that are the reason for the existence of this library, are derived from
  //! Runner.  The Runner class exists to collect various common tasks required
  //! by such a derived class with a possibly long running \ref run.
  //! These common tasks include:
  //! * running for a given amount of time (\ref run_for)
  //! * running until a nullary predicate is true (\ref run_until)
  //! * reporting after a given amount of time (\ref report_every)
  //! * checking if the given amount of time has elapsed since last report
  //! (\ref report)
  //! * checking the status of the algorithm: has it
  //! \ref started?  \ref finished? been killed by another thread
  //! (\ref dead)? has it timed out (\ref timed_out)? has it
  //! \ref stopped for any reason?
  //! * permit the function \ref run to be killed from another thread
  //! (\ref kill).
  class Runner {
    // Enum class for the state of the Runner.
    enum class state {
      never_run            = 0,
      running_to_finish    = 1,
      running_for          = 2,
      running_until        = 3,
      timed_out            = 4,
      stopped_by_predicate = 6,
      not_running          = 7,
      dead                 = 8
    };

   public:
    ////////////////////////////////////////////////////////////////////////
    // Runner - constructors + destructor - public
    ////////////////////////////////////////////////////////////////////////

    //! Default constructor.
    //!
    //! Returns a runner that is not started, not finished, not dead, not timed
    //! out, will run \ref FOREVER if not instructed otherwise,  that
    //! last reported at the time of construction, and that will report every
    //! std::chrono::seconds(1) if reporting is enabled.
    //!
    //! \par Parameters
    //! (None)
    Runner();

    //! Copy constructor.
    //!
    //! Returns a runner that is a copy of \p other. The state of the new runner
    //! is the same as \p other, except that the function passed as an argument
    //! to \ref run_until (if any) is not copied.
    //!
    //! \param other the Runner to copy.
    Runner(Runner const& other)
        : _last_report(other._last_report),
          _report_time_interval(other._report_time_interval),
          _run_for(other._run_for),
          _start_time(other._start_time),
          _state(),
          _stopper() {
      _state = other._state.load();
    }

    //! Move constructor
    //!
    //! Returns a runner that is initialised from \p other. The state of the
    //! new runner is the same as \p copy, except that the function passed as
    //! an argument to \ref run_until (if any) is not copied.
    //!
    //! \param other the Runner to move from.
    Runner(Runner&& other)
        : _last_report(std::move(other._last_report)),
          _report_time_interval(std::move(other._report_time_interval)),
          _run_for(std::move(other._run_for)),
          _start_time(std::move(other._start_time)),
          _state(),
          _stopper() {
      _state = other._state.load();
    }

    //! Copy assignment operator.
    //!
    //! Returns a runner that is initialised from \p other. The state of the
    //! new runner is the same as \p copy, except that the function passed as
    //! an argument to \ref run_until (if any) is not copied.
    //!
    //! \param other the Runner to move from.
    Runner& operator=(Runner const& other) {
      _last_report          = other._last_report;
      _report_time_interval = other._report_time_interval;
      _run_for              = other._run_for;
      _start_time           = other._start_time;
      _state                = other._state.load();
      return *this;
    }

    //! Move assignment operator.
    //!
    //! Returns a runner that is initialised from \p other. The state of the
    //! new runner is the same as \p copy, except that the function passed as
    //! an argument to \ref run_until (if any) is not copied.
    //!
    //! \param other the Runner to move from.
    Runner& operator=(Runner&& other) {
      _last_report          = std::move(other._last_report);
      _report_time_interval = std::move(other._report_time_interval);
      _run_for              = std::move(other._run_for);
      _start_time           = std::move(other._start_time);
      _state                = other._state.load();
      return *this;
    }

    virtual ~Runner() = default;

    ////////////////////////////////////////////////////////////////////////
    // Runner - pure virtual member functions - public
    ////////////////////////////////////////////////////////////////////////

    //! Run until \ref finished.
    //!
    //! Run the main algorithm implemented by a derived class derived of
    //! Runner.
    //!
    //! \returns
    //! (None)
    //!
    //! \par Parameters
    //! (None)
    // At the end of this either finished, or dead.
    void run() {
      if (!finished() && !dead()) {
        before_run();
        set_state(state::running_to_finish);
        try {
          run_impl();
        } catch (LibsemigroupsException const& e) {
          if (!dead()) {
            set_state(state::not_running);
          }
          throw;
        }
        if (!dead()) {
          set_state(state::not_running);
        }
      }
    }

    ////////////////////////////////////////////////////////////////////////
    // Runner - non-virtual member functions - public
    ////////////////////////////////////////////////////////////////////////

    //! Run for a specified amount of time.
    //!
    //! For this to work it is necessary to periodically check if
    //! timed_out() returns \c true, and to stop if it is, in the
    //! run() member function of any derived class of Runner.
    //!
    //! \param t the time in nanoseconds to run for.
    //!
    //! \returns
    //! (None)
    //!
    //! \sa run_for(TIntType)
    // At the end of this either finished, dead, or timed_out.
    void run_for(std::chrono::nanoseconds t);

    //! Run for a specified amount of time.
    //!
    //!
    //! For this to work it is necessary to periodically check if
    //! timed_out() returns \c true, and to stop if it is, in the
    //! run() member function of any derived class of Runner.
    //!
    //! \param t the time to run for (in \c TIntType).
    //!
    //! \returns
    //! (None)
    //!
    //! \sa run_for(std::chrono::nanoseconds)
    template <typename TIntType>
    void run_for(TIntType t) {
      run_for(std::chrono::nanoseconds(t));
    }

    //! Check if the amount of time passed to \ref run_for has elapsed.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! A \c bool
    //!
    //! \sa run_for(std::chrono::nanoseconds) and
    //! run_for(TIntType).
    bool timed_out() const {
      return (running_for()
                  ? std::chrono::duration_cast<std::chrono::nanoseconds>(
                        std::chrono::high_resolution_clock::now() - _start_time)
                        >= _run_for
                  : get_state() == state::timed_out);
    }

    //! Run until a nullary predicate returns \p true or \ref finished.
    //!
    //! \param func a callable type that will exist for at
    //! least until this function returns, or a function pointer.
    //!
    //! \returns
    //! (None)
    // At the end of this either finished, dead, or stopped_by_predicate.
    template <typename T>
    void run_until(T&& func) {
      if (!finished() && !dead()) {
        before_run();
        _stopper = std::forward<T>(func);
        if (!_stopper()) {
          set_state(state::running_until);
          run_impl();
          if (!finished()) {
            if (!dead()) {
              set_state(state::stopped_by_predicate);
            }
          } else {
            set_state(state::not_running);
          }
        }
        _stopper.invalidate();
      }
    }

    //! Run until a nullary predicate returns \p true or \ref finished.
    //!
    //! \param func a function pointer.
    //!
    //! \returns
    //! (None)
    void run_until(bool (*func)()) {
      run_until(detail::FunctionRef<bool(void)>(func));
    }

    //! Check if it is time to report.
    //!
    //! This function can be used in an implementation of run() (in a
    //! derived class of Runner) to check if enough time has
    //! passed that we should report again.
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \sa report_every(std::chrono::nanoseconds) and report_every(TIntType).
    inline bool report() const {
      auto t       = std::chrono::high_resolution_clock::now();
      auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
          t - _last_report);
      if (elapsed > _report_time_interval) {
        _last_report = t;
        return true;
      } else {
        return false;
      }
    }

    //! Set the minimum elapsed time between reports.
    //!
    //! This function can be used to specify at run time the minimum elapsed
    //! time between two calls to report() that return \c true. If
    //! report() returns \c true at time \c s, then report() will
    //! only return \c true again after time \c s + \c t has elapsed.
    //!
    //! \param t the amount of time (in nanoseconds) between reports.
    //!
    //! \returns
    //! (None)
    //!
    //! \sa
    //! report_every(TIntType)
    void report_every(std::chrono::nanoseconds t);

    //! Set the minimum elapsed time between reports.
    //!
    //! This function can be used to specify at run time the minimum elapsed
    //! time between two calls to report() that return \c true. If
    //! report() returns \c true at time \c s, then report() will
    //! only return \c true again after time \c s + \c t has elapsed.
    //!
    //! \param t the amount of time (in \c TIntType) between reports.
    //!
    //! \returns
    //! (None)
    //!
    //! \sa report_every(std::chrono::nanoseconds)
    template <typename TIntType>
    void report_every(TIntType t) {
      report_every(std::chrono::nanoseconds(t));
    }

    //! Get the minimum elapsed time between reports.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! The number of nanoseconds between reports.
    std::chrono::nanoseconds report_every() const noexcept {
      return _report_time_interval;
    }

    //! Report why \ref run stopped.
    //!
    //! Reports whether run() was stopped because it is finished(),
    //! timed_out(), or dead().
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! (None)
    void report_why_we_stopped() const;

    //! Check if \ref run has been run to completion or not.
    //!
    //! Returns \c true if run() has been run to completion. For this to
    //! work, the implementation of run() in a derived class of
    //! Runner must implement a specialisation of
    //! \c finished_impl.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \sa started()
    bool finished() const {
      if (started() && !dead() && finished_impl()) {
        _state = state::not_running;
        return true;
      } else {
        return false;
      }
      // since kill() may leave the object in an invalid state we only return
      // true here if we are not dead and the object thinks it is finished.
    }

    //! Check if \ref run has been called at least once before.
    //!
    //! Returns \c true if run() has started to run (it can be running or
    //! not).
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \sa finished()
    bool started() const {
      return get_state() != state::never_run;
    }

    //! Check if currently running.
    //!
    //! \returns
    //! \c true if run() is in the process of running and \c false it is not.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \sa finished()
    bool running() const noexcept {
      return get_state() == state::running_to_finish
             || get_state() == state::running_for
             || get_state() == state::running_until;
    }

    //! Stop \ref run from running (thread-safe).
    //!
    //! This function can be used to terminate run() from another thread.
    //! After kill() has been called the Runner may no longer be in a valid
    //! state, but will return \c true from dead() .
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! (None).
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \sa finished()
    void kill() noexcept {
      set_state(state::dead);
    }

    //! Check if the runner is dead.
    //!
    //! This function can be used to check if we should terminate run()
    //! because it has been killed by another thread.
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \sa kill()
    bool dead() const noexcept {
      return get_state() == state::dead;
    }

    //! Check if the runner is stopped.
    //!
    //! This function can be used to check whether or not run() has been
    //! stopped for whatever reason. In other words, it checks if
    //! timed_out(), finished(), or dead().
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \par Parameters
    //! (None)
    bool stopped() const {
      return (running() ? (timed_out() || stopped_by_predicate())
                        : get_state() > state::running_until);
    }

    //! Check if the runner was, or should, stop because of
    //! the argument for \ref run_until.
    //!
    //! If \c this is running, then the nullary predicate is called and its
    //! return value is returned. If \c this is not running, then \c true is
    //! returned if and only if the last time \c this was running it was
    //! stopped by a call to the nullary predicate passed to run_until().
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    // noexcept should depend on whether _stopper can throw or not
    bool stopped_by_predicate() const {
      if (running_until()) {
        LIBSEMIGROUPS_ASSERT(_stopper.valid());
        return _stopper();
      } else {
        return get_state() == state::stopped_by_predicate;
      }
    }

    //! Check if the runner is currently running for a particular length of
    //! time.
    //!
    //! If the Runner is currently running because its member function \ref
    //! run_for has been invoked, then this function returns \c true.
    //! Otherwise, \c false is returned.
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    bool running_for() const noexcept {
      return _state == state::running_for;
    }

    //! Check if the runner is currently running until a nullary predicate
    //! returns \c true.
    //!
    //! If the Runner is currently running because its member function \ref
    //! run_until has been invoked, then this function returns \c true.
    //! Otherwise, \c false is returned.
    //!
    //! \returns
    //! A \c bool.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \complexity
    //! Constant.
    //!
    //! \par Parameters
    //! (None)
    bool running_until() const noexcept {
      return _state == state::running_until;
    }

   private:
    virtual void run_impl()            = 0;
    virtual bool finished_impl() const = 0;
    virtual void before_run() {}

    state get_state() const noexcept {
      return _state;
    }

    void set_state(state stt) const {
      // We can set the state back to never_run if run_impl throws, and we are
      // restoring the old state.
      if (!dead()) {
        // It can be that *this* becomes dead after this function has been
        // called.
        _state = stt;
      }
    }

    ////////////////////////////////////////////////////////////////////////
    // Runner - data - private
    ////////////////////////////////////////////////////////////////////////

    mutable std::chrono::high_resolution_clock::time_point _last_report;
    std::chrono::nanoseconds                       _report_time_interval;
    std::chrono::nanoseconds                       _run_for;
    std::chrono::high_resolution_clock::time_point _start_time;
    mutable std::atomic<state>                     _state;
    detail::FunctionRef<bool(void)>                _stopper;
  };
}  // namespace libsemigroups
#endif  // LIBSEMIGROUPS_RUNNER_HPP_

quality100%

¤ Dauer der Verarbeitung: 0.7 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.