cpp/openttd-patchpack/source Changeset - r26916:2753c2f94e2d

Changeset - r26916:2753c2f94e2d

Parent rev.

Child rev.

[Not reviewed]

master

0 7 0

Michael Lutz - 18 months ago 2023-01-01 16:12:56
michi@icosahedron.de

Codechange: [Linkgraph] Store edges in each node and not in a global matrix.

7 files changed with 101 insertions and 139 deletions:

src/core/span_type.hpp

src/linkgraph/linkgraph.cpp

src/linkgraph/linkgraph.h

src/linkgraph/linkgraphjob.cpp

src/linkgraph/linkgraphjob.h

src/linkgraph/mcf.cpp

src/saveload/linkgraph_sl.cpp

0 comments (0 inline, 0 general)

src/core/span_type.hpp

➞

Show inline comments

@@ @@ -85,18 +85,20 @@ public: @@
 	constexpr size_t size() const noexcept { return static_cast<size_t>( last - first ); }
 	constexpr std::ptrdiff_t ssize() const noexcept { return static_cast<std::ptrdiff_t>( last - first ); }
 	constexpr bool empty() const noexcept { return size() == 0; }
 	constexpr iterator begin() const noexcept { return iterator(first); }
 	constexpr iterator end() const noexcept { return iterator(last); }
 	constexpr const_iterator cbegin() const noexcept { return const_iterator(first); }
 	constexpr const_iterator cend() const noexcept { return const_iterator(last); }
 	constexpr reference operator[](size_type idx) const { return first[idx]; }
 	constexpr pointer data() const noexcept { return first; }
 private:
 	pointer first;
 	pointer last;
 };
 #endif /* CORE_SPAN_TYPE_HPP */

src/linkgraph/linkgraph.cpp

➞

Show inline comments

@@ @@ -14,72 +14,72 @@ @@
 #include "../safeguards.h"
 /* Initialize the link-graph-pool */
 LinkGraphPool _link_graph_pool("LinkGraph");
 INSTANTIATE_POOL_METHODS(LinkGraph)
 /**
  * Create a node or clear it.
  * @param xy Location of the associated station.
  * @param st ID of the associated station.
  * @param demand Demand for cargo at the station.
  */
-inline void LinkGraph::BaseNode::Init(TileIndex xy, StationID st, uint demand)
+LinkGraph::BaseNode::BaseNode(TileIndex xy, StationID st, uint demand)
+{
 	this->xy = xy;
 	this->supply = 0;
 	this->demand = demand;
 	this->station = st;
 	this->last_update = INVALID_DATE;
+}
 /**
  * Create an edge.
  */
-inline void LinkGraph::BaseEdge::Init()
+LinkGraph::BaseEdge::BaseEdge()
+{
 	this->capacity = 0;
 	this->usage = 0;
 	this->travel_time_sum = 0;
 	this->last_unrestricted_update = INVALID_DATE;
 	this->last_restricted_update = INVALID_DATE;
 	this->next_edge = INVALID_NODE;
+}
 /**
  * Shift all dates by given interval.
  * This is useful if the date has been modified with the cheat menu.
  * @param interval Number of days to be added or subtracted.
  */
 void LinkGraph::ShiftDates(int interval)
+{
 	this->last_compression += interval;
 	for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
 		BaseNode &source = this->nodes[node1];
 		if (source.last_update != INVALID_DATE) source.last_update += interval;
 		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {
-			BaseEdge &edge = this->edges[node1][node2];
+			BaseEdge &edge = this->nodes[node1].edges[node2];
 			if (edge.last_unrestricted_update != INVALID_DATE) edge.last_unrestricted_update += interval;
 			if (edge.last_restricted_update != INVALID_DATE) edge.last_restricted_update += interval;
+		}
+	}
+}
 void LinkGraph::Compress()
+{
 	this->last_compression = (_date + this->last_compression) / 2;
 	for (NodeID node1 = 0; node1 < this->Size(); ++node1) {
 		this->nodes[node1].supply /= 2;
 		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {
-			BaseEdge &edge = this->edges[node1][node2];
+			BaseEdge &edge = this->nodes[node1].edges[node2];
 			if (edge.capacity > 0) {
 				uint new_capacity = std::max(1U, edge.capacity / 2);
 				if (edge.capacity < (1 << 16)) {
 					edge.travel_time_sum = edge.travel_time_sum * new_capacity / edge.capacity;
 				} else if (edge.travel_time_sum != 0) {
 					edge.travel_time_sum = std::max(1ULL, edge.travel_time_sum / 2);
+				}
 				edge.capacity = new_capacity;
 				edge.usage /= 2;
+			}
+		}
+	}
@@ @@ -92,177 +92,168 @@ void LinkGraph::Compress() @@
 void LinkGraph::Merge(LinkGraph *other)
+{
 	Date age = _date - this->last_compression + 1;
 	Date other_age = _date - other->last_compression + 1;
 	NodeID first = this->Size();
 	for (NodeID node1 = 0; node1 < other->Size(); ++node1) {
 		Station *st = Station::Get(other->nodes[node1].station);
 		NodeID new_node = this->AddNode(st);
 		this->nodes[new_node].supply = LinkGraph::Scale(other->nodes[node1].supply, age, other_age);
 		st->goods[this->cargo].link_graph = this->index;
 		st->goods[this->cargo].node = new_node;
 		for (NodeID node2 = 0; node2 < node1; ++node2) {
 			BaseEdge &forward = this->edges[new_node][first + node2];
 			BaseEdge &backward = this->edges[first + node2][new_node];
 			forward = other->edges[node1][node2];
 			backward = other->edges[node2][node1];
 			BaseEdge &forward = this->nodes[new_node].edges[first + node2];
 			BaseEdge &backward = this->nodes[first + node2].edges[new_node];
 			forward = other->nodes[node1].edges[node2];
 			backward = other->nodes[node2].edges[node1];
 			forward.capacity = LinkGraph::Scale(forward.capacity, age, other_age);
 			forward.usage = LinkGraph::Scale(forward.usage, age, other_age);
 			forward.travel_time_sum = LinkGraph::Scale(forward.travel_time_sum, age, other_age);
 			if (forward.next_edge != INVALID_NODE) forward.next_edge += first;
 			backward.capacity = LinkGraph::Scale(backward.capacity, age, other_age);
 			backward.usage = LinkGraph::Scale(backward.usage, age, other_age);
 			backward.travel_time_sum = LinkGraph::Scale(backward.travel_time_sum, age, other_age);
 			if (backward.next_edge != INVALID_NODE) backward.next_edge += first;
+		}
 		BaseEdge &new_start = this->edges[new_node][new_node];
 		new_start = other->edges[node1][node1];
 		BaseEdge &new_start = this->nodes[new_node].edges[new_node];
 		new_start = other->nodes[node1].edges[node1];
 		if (new_start.next_edge != INVALID_NODE) new_start.next_edge += first;
+	}
 	delete other;
+}
 /**
  * Remove a node from the link graph by overwriting it with the last node.
  * @param id ID of the node to be removed.
  */
 void LinkGraph::RemoveNode(NodeID id)
+{
 	assert(id < this->Size());
 	NodeID last_node = this->Size() - 1;
 	for (NodeID i = 0; i <= last_node; ++i) {
 		(*this)[i].RemoveEdge(id);
-		BaseEdge *node_edges = this->edges[i];
+		auto node_edges = this->nodes[i].edges;
 		NodeID prev = i;
 		NodeID next = node_edges[i].next_edge;
 		while (next != INVALID_NODE) {
 			if (next == last_node) {
 				node_edges[prev].next_edge = id;
 				break;
+			}
 			prev = next;
 			next = node_edges[prev].next_edge;
+		}
 		node_edges[id] = node_edges[last_node];
+	}
 	Station::Get(this->nodes[last_node].station)->goods[this->cargo].node = id;
 	/* Erase node by swapping with the last element. Node index is referenced
 	 * directly from station goods entries so the order and position must remain. */
 	this->nodes[id] = this->nodes.back();
 	this->nodes.pop_back();
 	this->edges.EraseColumn(id);
 	/* Not doing EraseRow here, as having the extra invalid row doesn't hurt
 	 * and removing it would trigger a lot of memmove. The data has already
 	 * been copied around in the loop above. */
 	for (auto &n : this->nodes) {
 		n.edges.pop_back();
+	}
+}
 /**
  * Add a node to the component and create empty edges associated with it. Set
  * the station's last_component to this component. Calculate the distances to all
  * other nodes. The distances to _all_ nodes are important as the demand
  * calculator relies on their availability.
  * @param st New node's station.
  * @return New node's ID.
  */
 NodeID LinkGraph::AddNode(const Station *st)
+{
 	const GoodsEntry &good = st->goods[this->cargo];
 	NodeID new_node = this->Size();
 	this->nodes.emplace_back();
 	/* Avoid reducing the height of the matrix as that is expensive and we
 	 * most likely will increase it again later which is again expensive. */
 	this->edges.Resize(new_node + 1U, std::max(new_node + 1U, this->edges.Height()));
 	this->nodes.emplace_back(st->xy, st->index, HasBit(good.status, GoodsEntry::GES_ACCEPTANCE));
 	this->nodes[new_node].Init(st->xy, st->index,
 			HasBit(good.status, GoodsEntry::GES_ACCEPTANCE));
 	BaseEdge *new_edges = this->edges[new_node];
 	for (auto &n : this->nodes) {
 		n.edges.resize(this->Size());
+	}
 	/* Reset the first edge starting at the new node */
-	new_edges[new_node].next_edge = INVALID_NODE;
+	this->nodes[new_node].edges[new_node].next_edge = INVALID_NODE;
 	for (NodeID i = 0; i <= new_node; ++i) {
 		new_edges[i].Init();
 		this->edges[i][new_node].Init();
+	}
 	return new_node;
+}
 /**
  * Fill an edge with values from a link. Set the restricted or unrestricted
  * update timestamp according to the given update mode.
  * @param to Destination node of the link.
  * @param capacity Capacity of the link.
  * @param usage Usage to be added.
  * @param mode Update mode to be used.
  */
 void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode)
+{
 	assert(this->index != to);
 	BaseEdge &edge = this->edges[to];
 	BaseEdge &first = this->edges[this->index];
 	BaseEdge &edge = this->node.edges[to];
 	BaseEdge &first = this->node.edges[this->index];
 	edge.capacity = capacity;
 	edge.usage = usage;
 	edge.travel_time_sum = static_cast<uint64>(travel_time) * capacity;
 	edge.next_edge = first.next_edge;
 	first.next_edge = to;
 	if (mode & EUM_UNRESTRICTED)  edge.last_unrestricted_update = _date;
 	if (mode & EUM_RESTRICTED) edge.last_restricted_update = _date;
+}
 /**
  * Creates an edge if none exists yet or updates an existing edge.
  * @param to Target node.
  * @param capacity Capacity of the link.
  * @param usage Usage to be added.
  * @param mode Update mode to be used.
  */
 void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage, uint32 travel_time, EdgeUpdateMode mode)
+{
 	assert(capacity > 0);
 	assert(usage <= capacity);
 	if (this->edges[to].capacity == 0) {
+	if (this->node.edges[to].capacity == 0) {
 		this->AddEdge(to, capacity, usage, travel_time, mode);
 	} else {
 		(*this)[to].Update(capacity, usage, travel_time, mode);
+	}
+}
 /**
  * Remove an outgoing edge from this node.
  * @param to ID of destination node.
  */
 void LinkGraph::Node::RemoveEdge(NodeID to)
+{
 	if (this->index == to) return;
 	BaseEdge &edge = this->edges[to];
+	BaseEdge &edge = this->node.edges[to];
 	edge.capacity = 0;
 	edge.last_unrestricted_update = INVALID_DATE;
 	edge.last_restricted_update = INVALID_DATE;
 	edge.usage = 0;
 	edge.travel_time_sum = 0;
 	NodeID prev = this->index;
 	NodeID next = this->edges[this->index].next_edge;
+	NodeID next = this->node.edges[this->index].next_edge;
 	while (next != INVALID_NODE) {
 		if (next == to) {
 			/* Will be removed, skip it. */
 			this->edges[prev].next_edge = edge.next_edge;
+			this->node.edges[prev].next_edge = edge.next_edge;
 			edge.next_edge = INVALID_NODE;
 			break;
 		} else {
 			prev = next;
 			next = this->edges[next].next_edge;
+			next = this->node.edges[next].next_edge;
+		}
+	}
+}
 /**
  * Update an edge. If mode contains UM_REFRESH refresh the edge to have at
  * least the given capacity and usage, otherwise add the capacity, usage and travel time.
  * In any case set the respective update timestamp(s), according to the given
  * mode.
  * @param capacity Capacity to be added/updated.
  * @param usage Usage to be added.
  * @param travel_time Travel time to be added, in ticks.
@@ @@ -296,21 +287,18 @@ void LinkGraph::Edge::Update(uint capaci @@
 	if (mode & EUM_UNRESTRICTED) this->edge.last_unrestricted_update = _date;
 	if (mode & EUM_RESTRICTED) this->edge.last_restricted_update = _date;
+}
 /**
  * Resize the component and fill it with empty nodes and edges. Used when
  * loading from save games. The component is expected to be empty before.
  * @param size New size of the component.
  */
 void LinkGraph::Init(uint size)
+{
 	assert(this->Size() == 0);
 	this->edges.Resize(size, size);
 	this->nodes.resize(size);
 	for (uint i = 0; i < size; ++i) {
 		this->nodes[i].Init();
 		BaseEdge *column = this->edges[i];
 		for (uint j = 0; j < size; ++j) column[j].Init();
 	for (auto &n : this->nodes) {
 		n.edges.resize(size);
+	}
+}

src/linkgraph/linkgraph.h

➞

Show inline comments

@@ @@ -3,25 +3,24 @@ @@
  * 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 linkgraph.h Declaration of link graph classes used for cargo distribution. */
 #ifndef LINKGRAPH_H
 #define LINKGRAPH_H
 #include "../core/pool_type.hpp"
 #include "../core/smallmap_type.hpp"
 #include "../core/smallmatrix_type.hpp"
 #include "../station_base.h"
 #include "../cargotype.h"
 #include "../date_func.h"
 #include "../saveload/saveload.h"
 #include "linkgraph_type.h"
 #include <utility>
 class LinkGraph;
 /**
  * Type of the pool for link graph components. Each station can be in at up to
  * 32 link graphs. So we allow for plenty of them to be created.
@@ @@ -29,53 +28,56 @@ class LinkGraph; @@
 typedef Pool<LinkGraph, LinkGraphID, 32, 0xFFFF> LinkGraphPool;
 /** The actual pool with link graphs. */
 extern LinkGraphPool _link_graph_pool;
 /**
  * A connected component of a link graph. Contains a complete set of stations
  * connected by links as nodes and edges. Each component also holds a copy of
  * the link graph settings at the time of its creation. The global settings
  * might change between the creation and join time so we can't rely on them.
  */
 class LinkGraph : public LinkGraphPool::PoolItem<&_link_graph_pool> {
 public:
 	/**
 	 * Node of the link graph. contains all relevant information from the associated
 	 * station. It's copied so that the link graph job can work on its own data set
 	 * in a separate thread.
 	 */
 	struct BaseNode {
 		uint supply;             ///< Supply at the station.
 		uint demand;             ///< Acceptance at the station.
 		StationID station;       ///< Station ID.
 		TileIndex xy;            ///< Location of the station referred to by the node.
 		Date last_update;        ///< When the supply was last updated.
 		void Init(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);
 	};
 	/**
 	 * An edge in the link graph. Corresponds to a link between two stations or at
 	 * least the distance between them. Edges from one node to itself contain the
 	 * ID of the opposite Node of the first active edge (i.e. not just distance) in
 	 * the column as next_edge.
 	 */
 	struct BaseEdge {
 		uint capacity;                 ///< Capacity of the link.
 		uint usage;                    ///< Usage of the link.
 		uint64 travel_time_sum;        ///< Sum of the travel times of the link, in ticks.
 		Date last_unrestricted_update; ///< When the unrestricted part of the link was last updated.
 		Date last_restricted_update;   ///< When the restricted part of the link was last updated.
 		NodeID next_edge;              ///< Destination of next valid edge starting at the same source node.
 		void Init();
 		BaseEdge();
 	};
 	/**
 	 * Node of the link graph. contains all relevant information from the associated
 	 * station. It's copied so that the link graph job can work on its own data set
 	 * in a separate thread.
 	 */
 	struct BaseNode {
 		uint supply;             ///< Supply at the station.
 		uint demand;             ///< Acceptance at the station.
 		StationID station;       ///< Station ID.
 		TileIndex xy;            ///< Location of the station referred to by the node.
 		Date last_update;        ///< When the supply was last updated.
 		std::vector<BaseEdge> edges;
 		BaseNode(TileIndex xy = INVALID_TILE, StationID st = INVALID_STATION, uint demand = 0);
 	};
 	/**
 	 * Wrapper for an edge (const or not) allowing retrieval, but no modification.
 	 * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".
 	 */
 	template<typename Tedge>
 	class EdgeWrapper {
 	protected:
 		Tedge &edge; ///< Actual edge to be used.
 	public:
@@ @@ -116,44 +118,40 @@ public: @@
 		 */
 		Date LastRestrictedUpdate() const { return this->edge.last_restricted_update; }
 		/**
 		 * Get the date of the last update to any part of the edge's capacity.
 		 * @return Last update.
 		 */
 		Date LastUpdate() const { return std::max(this->edge.last_unrestricted_update, this->edge.last_restricted_update); }
 	};
 	/**
 	 * Wrapper for a node (const or not) allowing retrieval, but no modification.
 	 * @tparam Tedge Actual node class, may be "const BaseNode" or just "BaseNode".
 	 * @tparam Tedge Actual edge class, may be "const BaseEdge" or just "BaseEdge".
 	 * @tparam Tnode Actual node class, may be "const BaseNode" or just "BaseNode".
 	 */
-	template<typename Tnode, typename Tedge>
 	template<typename Tnode>
 	class NodeWrapper {
 	protected:
 		Tnode &node;  ///< Node being wrapped.
 		Tedge *edges; ///< Outgoing edges for wrapped node.
 		NodeID index; ///< ID of wrapped node.
 		Tnode &node;       ///< Node being wrapped.
 		NodeID index;      ///< ID of wrapped node.
 	public:
 		/**
 		 * Wrap a node.
 		 * @param node Node to be wrapped.
 		 * @param edges Outgoing edges for node to be wrapped.
 		 * @param index ID of node to be wrapped.
 		 */
 		NodeWrapper(Tnode &node, Tedge *edges, NodeID index) : node(node),
 			edges(edges), index(index) {}
 		NodeWrapper(Tnode &node, NodeID index) : node(node), index(index) {}
 		/**
 		 * Get supply of wrapped node.
 		 * @return Supply.
 		 */
 		uint Supply() const { return this->node.supply; }
 		/**
 		 * Get demand of wrapped node.
 		 * @return Demand.
 		 */
 		uint Demand() const { return this->node.demand; }
@@ @@ -178,26 +176,26 @@ public: @@
 	};
 	/**
 	 * Base class for iterating across outgoing edges of a node. Only the real
 	 * edges (those with capacity) are iterated. The ones with only distance
 	 * information are skipped.
 	 * @tparam Tedge Actual edge class. May be "BaseEdge" or "const BaseEdge".
 	 * @tparam Titer Actual iterator class.
 	 */
 	template <class Tedge, class Tedge_wrapper, class Titer>
 	class BaseEdgeIterator {
 	protected:
 		Tedge *base;    ///< Array of edges being iterated.
 		NodeID current; ///< Current offset in edges array.
 		span<Tedge> base; ///< Array of edges being iterated.
 		NodeID current;   ///< Current offset in edges array.
 		/**
 		 * A "fake" pointer to enable operator-> on temporaries. As the objects
 		 * returned from operator* aren't references but real objects, we have
 		 * to return something that implements operator->, but isn't a pointer
 		 * from operator->. A fake pointer.
 		 */
 		class FakePointer : public std::pair<NodeID, Tedge_wrapper> {
 		public:
 			/**
 			 * Construct a fake pointer from a pair of NodeID and edge.
@@ @@ -209,25 +207,25 @@ public: @@
 			 * Retrieve the pair by operator->.
 			 * @return Pair being "pointed" to.
 			 */
 			std::pair<NodeID, Tedge_wrapper> *operator->() { return this; }
 		};
 	public:
 		/**
 		 * Constructor.
 		 * @param base Array of edges to be iterated.
 		 * @param current ID of current node (to locate the first edge).
 		 */
-		BaseEdgeIterator (Tedge *base, NodeID current) :
+		BaseEdgeIterator (span<Tedge> base, NodeID current) :
 			base(base),
 			current(current == INVALID_NODE ? current : base[current].next_edge)
 		{}
 		/**
 		 * Prefix-increment.
 		 * @return This.
 		 */
 		Titer &operator++()
+		{
 			this->current = this->base[this->current].next_edge;
 			return static_cast<Titer &>(*this);
@@ @@ -245,38 +243,38 @@ public: @@
+		}
 		/**
 		 * Compare with some other edge iterator. The other one may be of a
 		 * child class.
 		 * @tparam Tother Class of other iterator.
 		 * @param other Instance of other iterator.
 		 * @return If the iterators have the same edge array and current node.
 		 */
 		template<class Tother>
 		bool operator==(const Tother &other)
+		{
 			return this->base == other.base && this->current == other.current;
+			return this->base.data() == other.base.data() && this->current == other.current;
+		}
 		/**
 		 * Compare for inequality with some other edge iterator. The other one
 		 * may be of a child class.
 		 * @tparam Tother Class of other iterator.
 		 * @param other Instance of other iterator.
 		 * @return If either the edge arrays or the current nodes differ.
 		 */
 		template<class Tother>
 		bool operator!=(const Tother &other)
+		{
 			return this->base != other.base || this->current != other.current;
+			return this->base.data() != other.base.data() || this->current != other.current;
+		}
 		/**
 		 * Dereference with operator*.
 		 * @return Pair of current target NodeID and edge object.
 		 */
 		std::pair<NodeID, Tedge_wrapper> operator*() const
+		{
 			return std::pair<NodeID, Tedge_wrapper>(this->current, Tedge_wrapper(this->base[this->current]));
+		}
 		/**
@@ @@ -310,112 +308,108 @@ public: @@
 	/**
 	 * An iterator for const edges. Cannot be typedef'ed because of
 	 * template-reference to ConstEdgeIterator itself.
 	 */
 	class ConstEdgeIterator : public BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator> {
 	public:
 		/**
 		 * Constructor.
 		 * @param edges Array of edges to be iterated over.
 		 * @param current ID of current edge's end node.
 		 */
-		ConstEdgeIterator(const BaseEdge *edges, NodeID current) :
+		ConstEdgeIterator(span<const BaseEdge> edges, NodeID current) :
 			BaseEdgeIterator<const BaseEdge, ConstEdge, ConstEdgeIterator>(edges, current) {}
 	};
 	/**
 	 * An iterator for non-const edges. Cannot be typedef'ed because of
 	 * template-reference to EdgeIterator itself.
 	 */
 	class EdgeIterator : public BaseEdgeIterator<BaseEdge, Edge, EdgeIterator> {
 	public:
 		/**
 		 * Constructor.
 		 * @param edges Array of edges to be iterated over.
 		 * @param current ID of current edge's end node.
 		 */
-		EdgeIterator(BaseEdge *edges, NodeID current) :
+		EdgeIterator(span<BaseEdge> edges, NodeID current) :
 			BaseEdgeIterator<BaseEdge, Edge, EdgeIterator>(edges, current) {}
 	};
 	/**
 	 * Constant node class. Only retrieval operations are allowed on both the
 	 * node itself and its edges.
 	 */
-	class ConstNode : public NodeWrapper<const BaseNode, const BaseEdge> {
 	class ConstNode : public NodeWrapper<const BaseNode> {
 	public:
 		/**
 		 * Constructor.
 		 * @param lg LinkGraph to get the node from.
 		 * @param node ID of the node.
 		 */
 		ConstNode(const LinkGraph *lg, NodeID node) :
 			NodeWrapper<const BaseNode, const BaseEdge>(lg->nodes[node], lg->edges[node], node)
 		{}
 		ConstNode(const LinkGraph *lg, NodeID node) : NodeWrapper<const BaseNode>(lg->nodes[node], node) {}
 		/**
 		 * Get a ConstEdge. This is not a reference as the wrapper objects are
 		 * not actually persistent.
 		 * @param to ID of end node of edge.
 		 * @return Constant edge wrapper.
 		 */
 		ConstEdge operator[](NodeID to) const { return ConstEdge(this->edges[to]); }
+		ConstEdge operator[](NodeID to) const { return ConstEdge(this->node.edges[to]); }
 		/**
 		 * Get an iterator pointing to the start of the edges array.
 		 * @return Constant edge iterator.
 		 */
 		ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->edges, this->index); }
+		ConstEdgeIterator Begin() const { return ConstEdgeIterator(this->node.edges, this->index); }
 		/**
 		 * Get an iterator pointing beyond the end of the edges array.
 		 * @return Constant edge iterator.
 		 */
 		ConstEdgeIterator End() const { return ConstEdgeIterator(this->edges, INVALID_NODE); }
+		ConstEdgeIterator End() const { return ConstEdgeIterator(this->node.edges, INVALID_NODE); }
 	};
 	/**
 	 * Updatable node class. The node itself as well as its edges can be modified.
 	 */
-	class Node : public NodeWrapper<BaseNode, BaseEdge> {
 	class Node : public NodeWrapper<BaseNode> {
 	public:
 		/**
 		 * Constructor.
 		 * @param lg LinkGraph to get the node from.
 		 * @param node ID of the node.
 		 */
 		Node(LinkGraph *lg, NodeID node) :
 			NodeWrapper<BaseNode, BaseEdge>(lg->nodes[node], lg->edges[node], node)
 		{}
 		Node(LinkGraph *lg, NodeID node) : NodeWrapper<BaseNode>(lg->nodes[node], node) {}
 		/**
 		 * Get an Edge. This is not a reference as the wrapper objects are not
 		 * actually persistent.
 		 * @param to ID of end node of edge.
 		 * @return Edge wrapper.
 		 */
 		Edge operator[](NodeID to) { return Edge(this->edges[to]); }
+		Edge operator[](NodeID to) { return Edge(this->node.edges[to]); }
 		/**
 		 * Get an iterator pointing to the start of the edges array.
 		 * @return Edge iterator.
 		 */
 		EdgeIterator Begin() { return EdgeIterator(this->edges, this->index); }
+		EdgeIterator Begin() { return EdgeIterator(this->node.edges, this->index); }
 		/**
 		 * Get an iterator pointing beyond the end of the edges array.
 		 * @return Constant edge iterator.
 		 */
 		EdgeIterator End() { return EdgeIterator(this->edges, INVALID_NODE); }
+		EdgeIterator End() { return EdgeIterator(this->node.edges, INVALID_NODE); }
 		/**
 		 * Update the node's supply and set last_update to the current date.
 		 * @param supply Supply to be added.
 		 */
 		void UpdateSupply(uint supply)
+		{
 			this->node.supply += supply;
 			this->node.last_update = _date;
+		}
 		/**
@@ @@ -433,25 +427,24 @@ public: @@
 		 */
 		void SetDemand(uint demand)
+		{
 			this->node.demand = demand;
+		}
 		void AddEdge(NodeID to, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode);
 		void UpdateEdge(NodeID to, uint capacity, uint usage, uint32 time, EdgeUpdateMode mode);
 		void RemoveEdge(NodeID to);
 	};
 	typedef std::vector<BaseNode> NodeVector;
 	typedef SmallMatrix<BaseEdge> EdgeMatrix;
 	/** Minimum effective distance for timeout calculation. */
 	static const uint MIN_TIMEOUT_DISTANCE = 32;
 	/** Number of days before deleting links served only by vehicles stopped in depot. */
 	static const uint STALE_LINK_DEPOT_TIMEOUT = 1024;
 	/** Minimum number of days between subsequent compressions of a LG. */
 	static const uint COMPRESSION_INTERVAL = 256;
 	/**
 	 * Scale a value from a link graph of age orig_age for usage in one of age
@@ @@ -530,20 +523,20 @@ public: @@
+	}
 	NodeID AddNode(const Station *st);
 	void RemoveNode(NodeID id);
 protected:
 	friend class LinkGraph::ConstNode;
 	friend class LinkGraph::Node;
 	friend SaveLoadTable GetLinkGraphDesc();
 	friend SaveLoadTable GetLinkGraphJobDesc();
 	friend class SlLinkgraphNode;
 	friend class SlLinkgraphEdge;
 	friend class LinkGraphJob;
 	CargoID cargo;         ///< Cargo of this component's link graph.
 	Date last_compression; ///< Last time the capacities and supplies were compressed.
 	NodeVector nodes;      ///< Nodes in the component.
 	EdgeMatrix edges;      ///< Edges in the component.
 };
 #endif /* LINKGRAPH_H */

src/linkgraph/linkgraphjob.cpp

➞

Show inline comments

@@ @@ -171,58 +171,31 @@ LinkGraphJob::~LinkGraphJob() @@
 		InvalidateWindowData(WC_STATION_VIEW, st->index, this->Cargo());
+	}
+}
 /**
  * Initialize the link graph job: Resize nodes and edges and populate them.
  * This is done after the constructor so that we can do it in the calculation
  * thread without delaying the main game.
  */
 void LinkGraphJob::Init()
+{
 	uint size = this->Size();
 	this->nodes.resize(size);
 	this->edges.Resize(size, size);
 	this->nodes.reserve(size);
 	for (uint i = 0; i < size; ++i) {
 		this->nodes[i].Init(this->link_graph[i].Supply());
 		EdgeAnnotation *node_edges = this->edges[i];
 		for (uint j = 0; j < size; ++j) {
 			node_edges[j].Init();
+		}
 		this->nodes.emplace_back(this->link_graph.nodes[i]);
+	}
+}
 /**
  * Initialize a linkgraph job edge.
  */
 void LinkGraphJob::EdgeAnnotation::Init()
+{
 	this->demand = 0;
 	this->flow = 0;
 	this->unsatisfied_demand = 0;
+}
 /**
  * Initialize a Linkgraph job node. The underlying memory is expected to be
  * freshly allocated, without any constructors having been called.
  * @param supply Initial undelivered supply.
  */
 void LinkGraphJob::NodeAnnotation::Init(uint supply)
+{
 	this->undelivered_supply = supply;
 	new (&this->flows) FlowStatMap;
 	new (&this->paths) PathList;
+}
 /**
  * Add this path as a new child to the given base path, thus making this path
  * a "fork" of the base path.
  * @param base Path to fork from.
  * @param cap Maximum capacity of the new leg.
  * @param free_cap Remaining free capacity of the new leg.
  * @param dist Distance of the new leg.
  */
 void Path::Fork(Path *base, uint cap, int free_cap, uint dist)
+{
 	this->capacity = std::min(base->capacity, cap);
 	this->free_capacity = std::min(base->free_capacity, free_cap);
 	this->distance = base->distance + dist;

src/linkgraph/linkgraphjob.h

➞

Show inline comments

@@ @@ -27,50 +27,53 @@ extern LinkGraphJobPool _link_graph_job_ @@
 /**
  * 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);
 		std::vector<EdgeAnnotation> edges;
 		NodeAnnotation(const LinkGraph::BaseNode &node) : undelivered_supply(node.supply), paths(), flows()
+		{
 			this->edges.resize(node.edges.size());
+		}
 	};
 	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.
@@ @@ -137,36 +140,40 @@ public: @@
 		 */
 		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.
+		span<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) :
+		EdgeIterator(span<const LinkGraph::BaseEdge> base, span<EdgeAnnotation> base_anno, NodeID current) :
 				LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(base, current),
 				base_anno(base_anno) {}
 		EdgeIterator() :
 				LinkGraph::BaseEdgeIterator<const LinkGraph::BaseEdge, Edge, EdgeIterator>(span<const LinkGraph::BaseEdge>(), INVALID_NODE),
 				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
@@ @@ -175,59 +182,59 @@ public: @@
 		 */
 		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.
 		NodeAnnotation       &node_anno; ///< Annotation being wrapped.
 		span<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])
+			node_anno(lgj->nodes[node]), edge_annos(lgj->nodes[node].edges)
 		{}
 		/**
 		 * 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]); }
+		Edge operator[](NodeID to) const { return Edge(this->node.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); }
+		EdgeIterator Begin() const { return EdgeIterator(this->node.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); }
+		EdgeIterator End() const { return EdgeIterator(this->node.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; }

src/linkgraph/mcf.cpp

➞

Show inline comments

@@ @@ -94,27 +94,25 @@ public: @@
 class GraphEdgeIterator {
 private:
 	LinkGraphJob &job; ///< Job being executed
 	EdgeIterator i;    ///< Iterator pointing to current edge.
 	EdgeIterator end;  ///< Iterator pointing beyond last edge.
 public:
 	/**
 	 * Construct a GraphEdgeIterator.
 	 * @param job Job to iterate on.
 	 */
 	GraphEdgeIterator(LinkGraphJob &job) : job(job),
 		i(nullptr, nullptr, INVALID_NODE), end(nullptr, nullptr, INVALID_NODE)
 	{}
 	GraphEdgeIterator(LinkGraphJob &job) : job(job), i(), end() {}
 	/**
 	 * Setup the node to start iterating at.
 	 * @param source Unused.
 	 * @param node Node to start iterating at.
 	 */
 	void SetNode(NodeID source, NodeID node)
+	{
 		this->i = this->job[node].Begin();
 		this->end = this->job[node].End();
+	}

src/saveload/linkgraph_sl.cpp

➞

Show inline comments

@@ @@ -34,55 +34,56 @@ public: @@
 		    SLE_VAR(Edge, capacity,                 SLE_UINT32),
 		    SLE_VAR(Edge, usage,                    SLE_UINT32),
 		SLE_CONDVAR(Edge, travel_time_sum,          SLE_UINT64, SLV_LINKGRAPH_TRAVEL_TIME, SL_MAX_VERSION),
 		    SLE_VAR(Edge, last_unrestricted_update, SLE_INT32),
 		SLE_CONDVAR(Edge, last_restricted_update,   SLE_INT32, SLV_187, SL_MAX_VERSION),
 		    SLE_VAR(Edge, next_edge,                SLE_UINT16),
 	};
 	inline const static SaveLoadCompatTable compat_description = _linkgraph_edge_sl_compat;
 	void Save(Node *bn) const override
+	{
 		uint16 size = 0;
-		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->edges[_linkgraph_from][to].next_edge) {
+		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->nodes[_linkgraph_from].edges[to].next_edge) {
 			size++;
+		}
 		SlSetStructListLength(size);
 		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->edges[_linkgraph_from][to].next_edge) {
 			SlObject(&_linkgraph->edges[_linkgraph_from][to], this->GetDescription());
 		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->nodes[_linkgraph_from].edges[to].next_edge) {
 			SlObject(&_linkgraph->nodes[_linkgraph_from].edges[to], this->GetDescription());
+		}
+	}
 	void Load(Node *bn) const override
+	{
 		uint16 max_size = _linkgraph->Size();
 		_linkgraph->nodes[_linkgraph_from].edges.resize(max_size);
 		if (IsSavegameVersionBefore(SLV_191)) {
 			/* We used to save the full matrix ... */
 			for (NodeID to = 0; to < max_size; ++to) {
-				SlObject(&_linkgraph->edges[_linkgraph_from][to], this->GetLoadDescription());
+				SlObject(&_linkgraph->nodes[_linkgraph_from].edges[to], this->GetLoadDescription());
+			}
 			return;
+		}
 		size_t used_size = IsSavegameVersionBefore(SLV_SAVELOAD_LIST_LENGTH) ? max_size : SlGetStructListLength(UINT16_MAX);
 		/* ... but as that wasted a lot of space we save a sparse matrix now. */
-		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->edges[_linkgraph_from][to].next_edge) {
+		for (NodeID to = _linkgraph_from; to != INVALID_NODE; to = _linkgraph->nodes[_linkgraph_from].edges[to].next_edge) {
 			if (used_size == 0) SlErrorCorrupt("Link graph structure overflow");
 			used_size--;
 			if (to >= max_size) SlErrorCorrupt("Link graph structure overflow");
-			SlObject(&_linkgraph->edges[_linkgraph_from][to], this->GetLoadDescription());
+			SlObject(&_linkgraph->nodes[_linkgraph_from].edges[to], this->GetLoadDescription());
+		}
 		if (!IsSavegameVersionBefore(SLV_SAVELOAD_LIST_LENGTH) && used_size > 0) SlErrorCorrupt("Corrupted link graph");
+	}
 };
 class SlLinkgraphNode : public DefaultSaveLoadHandler<SlLinkgraphNode, LinkGraph> {
 public:
 	inline static const SaveLoad description[] = {
 		SLE_CONDVAR(Node, xy,          SLE_UINT32, SLV_191, SL_MAX_VERSION),
 		    SLE_VAR(Node, supply,      SLE_UINT32),
 		    SLE_VAR(Node, demand,      SLE_UINT32),

0 comments (0 inline, 0 general)