From c32eea02dd2de11636f5182a38fc8d577ff1f457 Mon Sep 17 00:00:00 2001 From: fonsinchen Date: Sun, 9 Jun 2013 12:58:37 +0000 Subject: (svn r25354) -Add: link graph schedule and typedefs for LinkGraph and related classes --- src/linkgraph/init.h | 27 ++++++ src/linkgraph/linkgraph_base.h | 1 + src/linkgraph/linkgraphjob_base.h | 23 +++++ src/linkgraph/linkgraphschedule.cpp | 168 ++++++++++++++++++++++++++++++++++++ src/linkgraph/linkgraphschedule.h | 83 ++++++++++++++++++ 5 files changed, 302 insertions(+) create mode 100644 src/linkgraph/init.h create mode 100644 src/linkgraph/linkgraphjob_base.h create mode 100644 src/linkgraph/linkgraphschedule.cpp create mode 100644 src/linkgraph/linkgraphschedule.h (limited to 'src/linkgraph') diff --git a/src/linkgraph/init.h b/src/linkgraph/init.h new file mode 100644 index 000000000..a39a0f820 --- /dev/null +++ b/src/linkgraph/init.h @@ -0,0 +1,27 @@ +/** @file init.h Declaration of initializing link graph handler. */ + +#ifndef INIT_H +#define INIT_H + +#include "linkgraphjob_base.h" + +/** + * Stateless, thread safe initialization hander. Initializes node and edge + * annotations. + */ +class InitHandler : public ComponentHandler { +public: + + /** + * Initialize the link graph job. + * @param job Job to be initialized. + */ + virtual void Run(LinkGraphJob &job) const { job.Init(); } + + /** + * Virtual destructor has to be defined because of virtual Run(). + */ + virtual ~InitHandler() {} +}; + +#endif /* INIT_H */ diff --git a/src/linkgraph/linkgraph_base.h b/src/linkgraph/linkgraph_base.h index 1878b1368..6e56af9a9 100644 --- a/src/linkgraph/linkgraph_base.h +++ b/src/linkgraph/linkgraph_base.h @@ -13,6 +13,7 @@ #define LINKGRAPH_BASE_H #include "linkgraph.h" +#include "linkgraphschedule.h" typedef LinkGraph::Node Node; typedef LinkGraph::Edge Edge; diff --git a/src/linkgraph/linkgraphjob_base.h b/src/linkgraph/linkgraphjob_base.h new file mode 100644 index 000000000..0a29166ee --- /dev/null +++ b/src/linkgraph/linkgraphjob_base.h @@ -0,0 +1,23 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * OpenTTD 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, version 2. + * OpenTTD 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 OpenTTD. If not, see . + */ + +/** @file linkgraphjob_base.h Some typedefs for component handlers. */ + +#ifndef LINKGRAPHJOB_BASE_H +#define LINKGRAPHJOB_BASE_H + +#include "linkgraph.h" +#include "linkgraphjob.h" +#include "linkgraphschedule.h" + +typedef LinkGraphJob::Node Node; +typedef LinkGraphJob::Edge Edge; +typedef LinkGraphJob::EdgeIterator EdgeIterator; + +#endif /* LINKGRAPHJOB_BASE_H */ diff --git a/src/linkgraph/linkgraphschedule.cpp b/src/linkgraph/linkgraphschedule.cpp new file mode 100644 index 000000000..31a837ad1 --- /dev/null +++ b/src/linkgraph/linkgraphschedule.cpp @@ -0,0 +1,168 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * OpenTTD 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, version 2. + * OpenTTD 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 OpenTTD. If not, see . + */ + +/** @file linkgraphschedule.cpp Definition of link graph schedule used for cargo distribution. */ + +#include "../stdafx.h" +#include "linkgraphschedule.h" +#include "init.h" + +/** + * Spawn a thread if possible and run the link graph job in the thread. If + * that's not possible run the job right now in the current thread. + * @param job Job to be executed. + */ +void LinkGraphSchedule::SpawnThread(LinkGraphJob *job) +{ + if (!ThreadObject::New(&(LinkGraphSchedule::Run), job, &job->thread)) { + job->thread = NULL; + /* Of course this will hang a bit. + * On the other hand, if you want to play games which make this hang noticably + * on a platform without threads then you'll probably get other problems first. + * OK: + * If someone comes and tells me that this hangs for him/her, I'll implement a + * smaller grained "Step" method for all handlers and add some more ticks where + * "Step" is called. No problem in principle. + */ + LinkGraphSchedule::Run(job); + } +} + +/** + * Join the calling thread with the given job's thread if threading is enabled. + * @param job Job whose execution thread is to be joined. + */ +void LinkGraphSchedule::JoinThread(LinkGraphJob *job) +{ + if (job->thread != NULL) { + job->thread->Join(); + delete job->thread; + job->thread = NULL; + } +} + +/** + * Start the next job in the schedule. + */ +void LinkGraphSchedule::SpawnNext() +{ + if (this->schedule.empty()) return; + LinkGraph *next = this->schedule.front(); + assert(next == LinkGraph::Get(next->index)); + this->schedule.pop_front(); + if (LinkGraphJob::CanAllocateItem()) { + LinkGraphJob *job = new LinkGraphJob(*next); + this->SpawnThread(job); + this->running.push_back(job); + } else { + NOT_REACHED(); + } +} + +/** + * Join the next finished job, if available. + */ +void LinkGraphSchedule::JoinNext() +{ + if (this->running.empty()) return; + LinkGraphJob *next = this->running.front(); + if (!next->IsFinished()) return; + this->running.pop_front(); + LinkGraphID id = next->LinkGraphIndex(); + this->JoinThread(next); + delete next; + if (LinkGraph::IsValidID(id)) { + LinkGraph *lg = LinkGraph::Get(id); + this->Unqueue(lg); // Unqueue to avoid double-queueing recycled IDs. + this->Queue(lg); + } +} + +/** + * Run all handlers for the given Job. This method is tailored to + * ThreadObject::New. + * @param j Pointer to a link graph job. + */ +/* static */ void LinkGraphSchedule::Run(void *j) +{ + LinkGraphJob *job = (LinkGraphJob *)j; + LinkGraphSchedule *schedule = LinkGraphSchedule::Instance(); + for (uint i = 0; i < lengthof(schedule->handlers); ++i) { + schedule->handlers[i]->Run(*job); + } +} + +/** + * Start all threads in the running list. This is only useful for save/load. + * Usually threads are started when the job is created. + */ +void LinkGraphSchedule::SpawnAll() +{ + for (JobList::iterator i = this->running.begin(); i != this->running.end(); ++i) { + this->SpawnThread(*i); + } +} + +/** + * Clear all link graphs and jobs from the schedule. + */ +/* static */ void LinkGraphSchedule::Clear() +{ + LinkGraphSchedule *inst = LinkGraphSchedule::Instance(); + for (JobList::iterator i(inst->running.begin()); i != inst->running.end(); ++i) { + inst->JoinThread(*i); + } + inst->running.clear(); + inst->schedule.clear(); +} + +/** + * Create a link graph schedule and initialize its handlers. + */ +LinkGraphSchedule::LinkGraphSchedule() +{ + this->handlers[0] = new InitHandler; +} + +/** + * Delete a link graph schedule and its handlers. + */ +LinkGraphSchedule::~LinkGraphSchedule() +{ + this->Clear(); + for (uint i = 0; i < lengthof(this->handlers); ++i) { + delete this->handlers[i]; + } +} + +/** + * Retrieve the link graph schedule or create it if necessary. + */ +/* static */ LinkGraphSchedule *LinkGraphSchedule::Instance() +{ + static LinkGraphSchedule inst; + return &inst; +} + +/** + * Spawn or join a link graph job or compress a link graph if any link graph is + * due to do so. + */ +void OnTick_LinkGraph() +{ + if (_date_fract != LinkGraphSchedule::SPAWN_JOIN_TICK) return; + Date offset = _date % _settings_game.linkgraph.recalc_interval; + if (offset == 0) { + LinkGraphSchedule::Instance()->SpawnNext(); + } else if (offset == _settings_game.linkgraph.recalc_interval / 2) { + LinkGraphSchedule::Instance()->JoinNext(); + } +} + + diff --git a/src/linkgraph/linkgraphschedule.h b/src/linkgraph/linkgraphschedule.h new file mode 100644 index 000000000..3b71f2954 --- /dev/null +++ b/src/linkgraph/linkgraphschedule.h @@ -0,0 +1,83 @@ +/* $Id$ */ + +/* + * This file is part of OpenTTD. + * OpenTTD 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, version 2. + * OpenTTD 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 OpenTTD. If not, see . + */ + +/** @file linkgraphschedule.h Declaration of link graph schedule used for cargo distribution. */ + +#ifndef LINKGRAPHSCHEDULE_H +#define LINKGRAPHSCHEDULE_H + +#include "linkgraph.h" + +class LinkGraphJob; + +/** + * A handler doing "something" on a link graph component. It must not keep any + * state as it is called concurrently from different threads. + */ +class ComponentHandler { +public: + /** + * Destroy the handler. Must be given due to virtual Run. + */ + virtual ~ComponentHandler() {} + + /** + * Run the handler. A link graph handler must not read or write any data + * outside the given component as that would create a potential desync. + * @param job Link graph component to run the handler on. + */ + virtual void Run(LinkGraphJob &job) const = 0; +}; + +class LinkGraphSchedule { +private: + LinkGraphSchedule(); + ~LinkGraphSchedule(); + typedef std::list GraphList; + typedef std::list JobList; + friend const SaveLoad *GetLinkGraphScheduleDesc(); + +protected: + ComponentHandler *handlers[1]; ///< Handlers to be run for each job. + GraphList schedule; ///< Queue for new jobs. + JobList running; ///< Currently running jobs. + + void SpawnThread(LinkGraphJob *job); + void JoinThread(LinkGraphJob *job); + +public: + /* This is a tick where not much else is happening, so a small lag might go unnoticed. */ + static const uint SPAWN_JOIN_TICK = 21; ///< Tick when jobs are spawned or joined every day. + + static LinkGraphSchedule *Instance(); + static void Run(void *j); + static void Clear(); + + void SpawnNext(); + void JoinNext(); + void SpawnAll(); + + /** + * Queue a link graph for execution. + * @param lg Link graph to be queued. + */ + void Queue(LinkGraph *lg) + { + assert(LinkGraph::Get(lg->index) == lg); + this->schedule.push_back(lg); + } + + /** + * Remove a link graph from the execution queue. + * @param lg Link graph to be removed. + */ + void Unqueue(LinkGraph *lg) { this->schedule.remove(lg); } +}; + +#endif /* LINKGRAPHSCHEDULE_H */ -- cgit v1.2.3-70-g09d2