(svn r25354) -Add: link graph schedule and typedefs for LinkGraph and related classes

13 files changed, 361 insertions, 0 deletions

diff --git a/projects/openttd_vs100.vcxproj b/projects/openttd_vs100.vcxproj
index 2c0b86853..c71f04734 100644
--- a/projects/openttd_vs100.vcxproj
+++ b/projects/openttd_vs100.vcxproj
@@ -333,6 +333,7 @@
     <ClCompile Include="..\src\landscape.cpp" />
     <ClCompile Include="..\src\linkgraph\linkgraph.cpp" />
     <ClCompile Include="..\src\linkgraph\linkgraphjob.cpp" />
+    <ClCompile Include="..\src\linkgraph\linkgraphschedule.cpp" />
     <ClCompile Include="..\src\map.cpp" />
     <ClCompile Include="..\src\misc.cpp" />
     <ClCompile Include="..\src\mixer.cpp" />
@@ -472,11 +473,14 @@
     <ClInclude Include="..\src\landscape.h" />
     <ClInclude Include="..\src\landscape_type.h" />
     <ClInclude Include="..\src\language.h" />
+    <ClInclude Include="..\src\linkgraph\init.h" />
     <ClInclude Include="..\src\linkgraph\linkgraph.h" />
     <ClInclude Include="..\src\linkgraph\linkgraph_base.h" />
     <ClInclude Include="..\src\linkgraph\linkgraph_gui.h" />
     <ClInclude Include="..\src\linkgraph\linkgraph_type.h" />
     <ClInclude Include="..\src\linkgraph\linkgraphjob.h" />
+    <ClInclude Include="..\src\linkgraph\linkgraphjob_base.h" />
+    <ClInclude Include="..\src\linkgraph\linkgraphschedule.h" />
     <ClInclude Include="..\src\livery.h" />
     <ClInclude Include="..\src\map_func.h" />
     <ClInclude Include="..\src\map_type.h" />
diff --git a/projects/openttd_vs100.vcxproj.filters b/projects/openttd_vs100.vcxproj.filters
index 790f9f1eb..ab220b057 100644
--- a/projects/openttd_vs100.vcxproj.filters
+++ b/projects/openttd_vs100.vcxproj.filters
@@ -228,6 +228,9 @@
     <ClCompile Include="..\src\linkgraph\linkgraphjob.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
+    <ClCompile Include="..\src\linkgraph\linkgraphschedule.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
     <ClCompile Include="..\src\map.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
@@ -645,6 +648,9 @@
     <ClInclude Include="..\src\language.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\linkgraph\init.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="..\src\linkgraph\linkgraph.h">
       <Filter>Header Files</Filter>
     </ClInclude>
@@ -660,6 +666,12 @@
     <ClInclude Include="..\src\linkgraph\linkgraphjob.h">
       <Filter>Header Files</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\linkgraph\linkgraphjob_base.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
+    <ClInclude Include="..\src\linkgraph\linkgraphschedule.h">
+      <Filter>Header Files</Filter>
+    </ClInclude>
     <ClInclude Include="..\src\livery.h">
       <Filter>Header Files</Filter>
     </ClInclude>
diff --git a/projects/openttd_vs80.vcproj b/projects/openttd_vs80.vcproj
index c7ce0fdb6..6f06b5d4a 100644
--- a/projects/openttd_vs80.vcproj
+++ b/projects/openttd_vs80.vcproj
@@ -603,6 +603,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\linkgraph\linkgraphschedule.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\map.cpp"
 				>
 			</File>
@@ -1163,6 +1167,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\linkgraph\init.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\linkgraph\linkgraph.h"
 				>
 			</File>
@@ -1183,6 +1191,14 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\linkgraph\linkgraphjob_base.h"
+				>
+			</File>
+			<File
+				RelativePath=".\..\src\linkgraph\linkgraphschedule.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\livery.h"
 				>
 			</File>
diff --git a/projects/openttd_vs90.vcproj b/projects/openttd_vs90.vcproj
index 989905acf..56db5987e 100644
--- a/projects/openttd_vs90.vcproj
+++ b/projects/openttd_vs90.vcproj
@@ -600,6 +600,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\linkgraph\linkgraphschedule.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\map.cpp"
 				>
 			</File>
@@ -1160,6 +1164,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\linkgraph\init.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\linkgraph\linkgraph.h"
 				>
 			</File>
@@ -1180,6 +1188,14 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\linkgraph\linkgraphjob_base.h"
+				>
+			</File>
+			<File
+				RelativePath=".\..\src\linkgraph\linkgraphschedule.h"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\livery.h"
 				>
 			</File>
diff --git a/source.list b/source.list
index 99034a9c8..f650d33d7 100644
--- a/source.list
+++ b/source.list
@@ -41,6 +41,7 @@ ini_load.cpp
 landscape.cpp
 linkgraph/linkgraph.cpp
 linkgraph/linkgraphjob.cpp
+linkgraph/linkgraphschedule.cpp
 map.cpp
 misc.cpp
 mixer.cpp
@@ -205,11 +206,14 @@ ini_type.h
 landscape.h
 landscape_type.h
 language.h
+linkgraph/init.h
 linkgraph/linkgraph.h
 linkgraph/linkgraph_base.h
 linkgraph/linkgraph_gui.h
 linkgraph/linkgraph_type.h
 linkgraph/linkgraphjob.h
+linkgraph/linkgraphjob_base.h
+linkgraph/linkgraphschedule.h
 livery.h
 map_func.h
 map_type.h
diff --git a/src/landscape.cpp b/src/landscape.cpp
index a4b12f857..0d8abf9bf 100644
--- a/src/landscape.cpp
+++ b/src/landscape.cpp
@@ -1295,6 +1295,7 @@ void OnTick_Station();
 void OnTick_Industry();
 
 void OnTick_Companies();
+void OnTick_LinkGraph();
 
 void CallLandscapeTick()
 {
@@ -1304,4 +1305,5 @@ void CallLandscapeTick()
 	OnTick_Industry();
 
 	OnTick_Companies();
+	OnTick_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 <http://www.gnu.org/licenses/>.
+ */
+
+/** @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 <http://www.gnu.org/licenses/>.
+ */
+
+/** @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 <http://www.gnu.org/licenses/>.
+ */
+
+/** @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<LinkGraph *> GraphList;
+	typedef std::list<LinkGraphJob *> 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 */
diff --git a/src/misc.cpp b/src/misc.cpp
index c967d5369..11607a5f1 100644
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -27,6 +27,7 @@
 #include "window_func.h"
 #include "core/pool_type.hpp"
 #include "game/game.hpp"
+#include "linkgraph/linkgraphschedule.h"
 
 
 extern TileIndex _cur_tileloop_tile;
@@ -68,6 +69,7 @@ void InitializeGame(uint size_x, uint size_y, bool reset_date, bool reset_settin
 		InitializeOldNames();
 	}
 
+	LinkGraphSchedule::Clear();
 	PoolBase::Clean(PT_NORMAL);
 
 	ResetPersistentNewGRFData();
diff --git a/src/openttd.cpp b/src/openttd.cpp
index 2386e4798..35677f155 100644
--- a/src/openttd.cpp
+++ b/src/openttd.cpp
@@ -63,6 +63,8 @@
 #include "subsidy_func.h"
 
 
+#include "linkgraph/linkgraphschedule.h"
+
 #include <stdarg.h>
 
 
@@ -297,6 +299,7 @@ static void ShutdownGame()
 	free(_config_file);
 #endif
 
+	LinkGraphSchedule::Clear();
 	PoolBase::Clean(PT_ALL);
 
 	/* No NewGRFs were loaded when it was still bootstrapping. */