summaryrefslogtreecommitdiff
path: root/src/linkgraph/linkgraphjob.h
blob: 812afd1f71fac207ccc8a761dfca3252c4d24b87 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
/*
 * 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.h Declaration of link graph job classes used for cargo distribution. */

#ifndef LINKGRAPHJOB_H
#define LINKGRAPHJOB_H

#include "../thread.h"
#include "linkgraph.h"
#include <list>
#include <atomic>

class LinkGraphJob;
class Path;
typedef std::list<Path *> PathList;

/** Type of the pool for link graph jobs. */
typedef Pool<LinkGraphJob, LinkGraphJobID, 32, 0xFFFF> LinkGraphJobPool;
/** The actual pool with link graph jobs. */
extern LinkGraphJobPool _link_graph_job_pool;

/**
 * Class for calculation jobs to be run on link graphs.
 */
class LinkGraphJob : public LinkGraphJobPool::PoolItem<&_link_graph_job_pool>{
private:
	/**
	 * Annotation for a link graph edge.
	 */
	struct EdgeAnnotation {
		uint demand;             ///< Transport demand between the nodes.
		uint unsatisfied_demand; ///< Demand over this edge that hasn't been satisfied yet.
		uint flow;               ///< Planned flow over this edge.
		void Init();
	};

	/**
	 * Annotation for a link graph node.
	 */
	struct NodeAnnotation {
		uint undelivered_supply; ///< Amount of supply that hasn't been distributed yet.
		PathList paths;          ///< Paths through this node, sorted so that those with flow == 0 are in the back.
		FlowStatMap flows;       ///< Planned flows to other nodes.
		void Init(uint supply);
	};

	typedef std::vector<NodeAnnotation> NodeAnnotationVector;
	typedef SmallMatrix<EdgeAnnotation> EdgeAnnotationMatrix;

	friend SaveLoadTable GetLinkGraphJobDesc();
	friend class LinkGraphSchedule;

protected:
	const LinkGraph link_graph;       ///< Link graph to by analyzed. Is copied when job is started and mustn't be modified later.
	const LinkGraphSettings settings; ///< Copy of _settings_game.linkgraph at spawn time.
	std::thread thread;               ///< Thread the job is running in or a default-constructed thread if it's running in the main thread.
	Date join_date;                   ///< Date when the job is to be joined.
	NodeAnnotationVector nodes;       ///< Extra node data necessary for link graph calculation.
	EdgeAnnotationMatrix edges;       ///< Extra edge data necessary for link graph calculation.
	std::atomic<bool> job_completed;  ///< Is the job still running. This is accessed by multiple threads and reads may be stale.
	std::atomic<bool> job_aborted;    ///< Has the job been aborted. This is accessed by multiple threads and reads may be stale.

	void EraseFlows(NodeID from);
	void JoinThread();
	void SpawnThread();

public:

	/**
	 * A job edge. Wraps a link graph edge and an edge annotation. The
	 * annotation can be modified, the edge is constant.
	 */
	class Edge : public LinkGraph::ConstEdge {
	private:
		EdgeAnnotation &anno; ///< Annotation being wrapped.
	public:
		/**
		 * Constructor.
		 * @param edge Link graph edge to be wrapped.
		 * @param anno Annotation to be wrapped.
		 */
		Edge(const LinkGraph::BaseEdge &edge, EdgeAnnotation &anno) :
				LinkGraph::ConstEdge(edge), anno(anno) {}

		/**
		 * Get the transport demand between end the points of the edge.
		 * @return Demand.
		 */
		uint Demand() const { return this->anno.demand; }

		/**
		 * Get the transport demand that hasn't been satisfied by flows, yet.
		 * @return Unsatisfied demand.
		 */
		uint UnsatisfiedDemand() const { return this->anno.unsatisfied_demand; }

		/**
		 * Get the total flow on the edge.
		 * @return Flow.
		 */
		uint Flow() const { return this->anno.flow; }

		/**
		 * Add some flow.
		 * @param flow Flow to be added.
		 */
		void AddFlow(uint flow) { this->anno.flow += flow; }

		/**
		 * Remove some flow.
		 * @param flow Flow to be removed.
		 */
		void RemoveFlow(uint flow)
		{
			assert(flow <= this->anno.flow);
			this->anno.flow -= flow;
		}

		/**
		 * Add some (not yet satisfied) demand.
		 * @param demand Demand to be added.
		 */
		void AddDemand(uint demand)
		{
			this->anno.demand += demand;
			this->anno.unsatisfied_demand += demand;
		}

		/**
		 * Satisfy some demand.
		 * @param demand Demand to be satisfied.
		 */
		void SatisfyDemand(uint demand)
		{
			assert(demand <= this->anno.unsatisfied_demand);
			this->anno.unsatisfied_demand -= demand;
		}
	};

	/**
	 * Iterator for job edges.
	 */
	class EdgeIterator : public LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator> {
		EdgeAnnotation *base_anno; ///< Array of annotations to be (indirectly) iterated.
	public:
		/**
		 * Constructor.
		 * @param base Array of edges to be iterated.
		 * @param base_anno Array of annotations to be iterated.
		 * @param current Start offset of iteration.
		 */
		EdgeIterator(const LinkGraph::BaseEdge *base, EdgeAnnotation *base_anno, NodeID current) :
				LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(base, current),
				base_anno(base_anno) {}

		/**
		 * Dereference.
		 * @return Pair of the edge currently pointed to and the ID of its
		 *         other end.
		 */
		std::pair<NodeID, Edge> operator*() const
		{
			return std::pair<NodeID, Edge>(this->current, Edge(this->base[this->current], this->base_anno[this->current]));
		}

		/**
		 * Dereference. Has to be repeated here as operator* is different than
		 * in LinkGraph::EdgeWrapper.
		 * @return Fake pointer to pair of NodeID/Edge.
		 */
		FakePointer operator->() const {
			return FakePointer(this->operator*());
		}
	};

	/**
	 * Link graph job node. Wraps a constant link graph node and a modifiable
	 * node annotation.
	 */
	class Node : public LinkGraph::ConstNode {
	private:
		NodeAnnotation &node_anno;  ///< Annotation being wrapped.
		EdgeAnnotation *edge_annos; ///< Edge annotations belonging to this node.
	public:

		/**
		 * Constructor.
		 * @param lgj Job to take the node from.
		 * @param node ID of the node.
		 */
		Node (LinkGraphJob *lgj, NodeID node) :
			LinkGraph::ConstNode(&lgj->link_graph, node),
			node_anno(lgj->nodes[node]), edge_annos(lgj->edges[node])
		{}

		/**
		 * Retrieve an edge starting at this node. Mind that this returns an
		 * object, not a reference.
		 * @param to Remote end of the edge.
		 * @return Edge between this node and "to".
		 */
		Edge operator[](NodeID to) const { return Edge(this->edges[to], this->edge_annos[to]); }

		/**
		 * Iterator for the "begin" of the edge array. Only edges with capacity
		 * are iterated. The others are skipped.
		 * @return Iterator pointing to the first edge.
		 */
		EdgeIterator Begin() const { return EdgeIterator(this->edges, this->edge_annos, index); }

		/**
		 * Iterator for the "end" of the edge array. Only edges with capacity
		 * are iterated. The others are skipped.
		 * @return Iterator pointing beyond the last edge.
		 */
		EdgeIterator End() const { return EdgeIterator(this->edges, this->edge_annos, INVALID_NODE); }

		/**
		 * Get amount of supply that hasn't been delivered, yet.
		 * @return Undelivered supply.
		 */
		uint UndeliveredSupply() const { return this->node_anno.undelivered_supply; }

		/**
		 * Get the flows running through this node.
		 * @return Flows.
		 */
		FlowStatMap &Flows() { return this->node_anno.flows; }

		/**
		 * Get a constant version of the flows running through this node.
		 * @return Flows.
		 */
		const FlowStatMap &Flows() const { return this->node_anno.flows; }

		/**
		 * Get the paths this node is part of. Paths are always expected to be
		 * sorted so that those with flow == 0 are in the back of the list.
		 * @return Paths.
		 */
		PathList &Paths() { return this->node_anno.paths; }

		/**
		 * Get a constant version of the paths this node is part of.
		 * @return Paths.
		 */
		const PathList &Paths() const { return this->node_anno.paths; }

		/**
		 * Deliver some supply, adding demand to the respective edge.
		 * @param to Destination for supply.
		 * @param amount Amount of supply to be delivered.
		 */
		void DeliverSupply(NodeID to, uint amount)
		{
			this->node_anno.undelivered_supply -= amount;
			(*this)[to].AddDemand(amount);
		}
	};

	/**
	 * Bare constructor, only for save/load. link_graph, join_date and actually
	 * settings have to be brutally const-casted in order to populate them.
	 */
	LinkGraphJob() : settings(_settings_game.linkgraph),
			join_date(INVALID_DATE), job_completed(false), job_aborted(false) {}

	LinkGraphJob(const LinkGraph &orig);
	~LinkGraphJob();

	void Init();

	/**
	 * Check if job has actually finished.
	 * This is allowed to spuriously return an incorrect value.
	 * @return True if job has actually finished.
	 */
	inline bool IsJobCompleted() const { return this->job_completed.load(std::memory_order_acquire); }

	/**
	 * Check if job has been aborted.
	 * This is allowed to spuriously return false incorrectly, but is not allowed to incorrectly return true.
	 * @return True if job has been aborted.
	 */
	inline bool IsJobAborted() const { return this->job_aborted.load(std::memory_order_acquire); }

	/**
	 * Abort job.
	 * The job may exit early at the next available opportunity.
	 * After this method has been called the state of the job is undefined, and the only valid operation
	 * is to join the thread and discard the job data.
	 */
	inline void AbortJob() { this->job_aborted.store(true, std::memory_order_release); }

	/**
	 * Check if job is supposed to be finished.
	 * @return True if job should be finished by now, false if not.
	 */
	inline bool IsScheduledToBeJoined() const { return this->join_date <= _date; }

	/**
	 * Get the date when the job should be finished.
	 * @return Join date.
	 */
	inline Date JoinDate() const { return join_date; }

	/**
	 * Change the join date on date cheating.
	 * @param interval Number of days to add.
	 */
	inline void ShiftJoinDate(int interval) { this->join_date += interval; }

	/**
	 * Get the link graph settings for this component.
	 * @return Settings.
	 */
	inline const LinkGraphSettings &Settings() const { return this->settings; }

	/**
	 * Get a node abstraction with the specified id.
	 * @param num ID of the node.
	 * @return the Requested node.
	 */
	inline Node operator[](NodeID num) { return Node(this, num); }

	/**
	 * Get the size of the underlying link graph.
	 * @return Size.
	 */
	inline NodeID Size() const { return this->link_graph.Size(); }

	/**
	 * Get the cargo of the underlying link graph.
	 * @return Cargo.
	 */
	inline CargoID Cargo() const { return this->link_graph.Cargo(); }

	/**
	 * Get the date when the underlying link graph was last compressed.
	 * @return Compression date.
	 */
	inline Date LastCompression() const { return this->link_graph.LastCompression(); }

	/**
	 * Get the ID of the underlying link graph.
	 * @return Link graph ID.
	 */
	inline LinkGraphID LinkGraphIndex() const { return this->link_graph.index; }

	/**
	 * Get a reference to the underlying link graph. Only use this for save/load.
	 * @return Link graph.
	 */
	inline const LinkGraph &Graph() const { return this->link_graph; }
};

/**
 * A leg of a path in the link graph. Paths can form trees by being "forked".
 */
class Path {
public:
	static Path *invalid_path;

	Path(NodeID n, bool source = false);
	virtual ~Path() = default;

	/** Get the node this leg passes. */
	inline NodeID GetNode() const { return this->node; }

	/** Get the overall origin of the path. */
	inline NodeID GetOrigin() const { return this->origin; }

	/** Get the parent leg of this one. */
	inline Path *GetParent() { return this->parent; }

	/** Get the overall capacity of the path. */
	inline uint GetCapacity() const { return this->capacity; }

	/** Get the free capacity of the path. */
	inline int GetFreeCapacity() const { return this->free_capacity; }

	/**
	 * Get ratio of free * 16 (so that we get fewer 0) /
	 * max(total capacity, 1) (so that we don't divide by 0).
	 * @param free Free capacity.
	 * @param total Total capacity.
	 * @return free * 16 / max(total, 1).
	 */
	inline static int GetCapacityRatio(int free, uint total)
	{
		return Clamp(free, PATH_CAP_MIN_FREE, PATH_CAP_MAX_FREE) * PATH_CAP_MULTIPLIER / std::max(total, 1U);
	}

	/**
	 * Get capacity ratio of this path.
	 * @return free capacity * 16 / (total capacity + 1).
	 */
	inline int GetCapacityRatio() const
	{
		return Path::GetCapacityRatio(this->free_capacity, this->capacity);
	}

	/** Get the overall distance of the path. */
	inline uint GetDistance() const { return this->distance; }

	/** Reduce the flow on this leg only by the specified amount. */
	inline void ReduceFlow(uint f) { this->flow -= f; }

	/** Increase the flow on this leg only by the specified amount. */
	inline void AddFlow(uint f) { this->flow += f; }

	/** Get the flow on this leg. */
	inline uint GetFlow() const { return this->flow; }

	/** Get the number of "forked off" child legs of this one. */
	inline uint GetNumChildren() const { return this->num_children; }

	/**
	 * Detach this path from its parent.
	 */
	inline void Detach()
	{
		if (this->parent != nullptr) {
			this->parent->num_children--;
			this->parent = nullptr;
		}
	}

	uint AddFlow(uint f, LinkGraphJob &job, uint max_saturation);
	void Fork(Path *base, uint cap, int free_cap, uint dist);

protected:

	/**
	 * Some boundaries to clamp against in order to avoid integer overflows.
	 */
	enum PathCapacityBoundaries {
		PATH_CAP_MULTIPLIER = 16,
		PATH_CAP_MIN_FREE = (INT_MIN + 1) / PATH_CAP_MULTIPLIER,
		PATH_CAP_MAX_FREE = (INT_MAX - 1) / PATH_CAP_MULTIPLIER
	};

	uint distance;     ///< Sum(distance of all legs up to this one).
	uint capacity;     ///< This capacity is min(capacity) fom all edges.
	int free_capacity; ///< This capacity is min(edge.capacity - edge.flow) for the current run of Dijkstra.
	uint flow;         ///< Flow the current run of the mcf solver assigns.
	NodeID node;       ///< Link graph node this leg passes.
	NodeID origin;     ///< Link graph node this path originates from.
	uint num_children; ///< Number of child legs that have been forked from this path.
	Path *parent;      ///< Parent leg of this one.
};

#endif /* LINKGRAPHJOB_H */