cpp/openttd-patchpack/source Changeset - r23569:b43bf680313b

Changeset - r23569:b43bf680313b

Parent rev.

Child rev.

[Not reviewed]

master

0 1 0

PeterN - 5 years ago 2019-03-30 22:19:50
peter@fuzzle.org

Fix aa7ca7fe6: Linkgraph node index order must be maintained due to other references. (#7431)

Linkgraph nodes require a specific order that was maintained by swapping just the last
element for the node to be removed. std::vector::erase() changed this to removing the
node is then shuffling the remain items down, which upsets other references to this
indices.

This is fixed by switching back to the original swap & pop method.

1 file changed with 4 insertions and 1 deletions:

src/linkgraph/linkgraph.cpp

0 comments (0 inline, 0 general)

src/linkgraph/linkgraph.cpp

➞

Show inline comments

@@ @@ -118,49 +118,52 @@ void LinkGraph::Merge(LinkGraph *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];
 		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;
 	this->nodes.erase(this->nodes.begin() + 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. */
+}
 /**
  * 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,
 			max(new_node + 1U, this->edges.Height()));

0 comments (0 inline, 0 general)