Changeset - r20854:d6b61e2cf909
[Not reviewed]
master
0 5 0
fonsinchen - 11 years ago 2013-10-22 16:13:28
fonsinchen@openttd.org
(svn r25898) -Codechange: Add second timestamp for 'restricted links' to all edges.
5 files changed with 104 insertions and 31 deletions:
0 comments (0 inline, 0 general)
src/linkgraph/linkgraph.cpp
Show inline comments
 
@@ -39,7 +39,8 @@ inline void LinkGraph::BaseEdge::Init(ui
 
	this->distance = distance;
 
	this->capacity = 0;
 
	this->usage = 0;
 
	this->last_update = INVALID_DATE;
 
	this->last_unrestricted_update = INVALID_DATE;
 
	this->last_restricted_update = INVALID_DATE;
 
	this->next_edge = INVALID_NODE;
 
}
 

	
 
@@ -56,7 +57,8 @@ void LinkGraph::ShiftDates(int interval)
 
		if (source.last_update != INVALID_DATE) source.last_update += interval;
 
		for (NodeID node2 = 0; node2 < this->Size(); ++node2) {
 
			BaseEdge &edge = this->edges[node1][node2];
 
			if (edge.last_update != INVALID_DATE) edge.last_update += interval;
 
			if (edge.last_unrestricted_update != INVALID_DATE) edge.last_unrestricted_update += interval;
 
			if (edge.last_restricted_update != INVALID_DATE) edge.last_restricted_update += interval;
 
		}
 
	}
 
}
 
@@ -178,9 +180,11 @@ NodeID LinkGraph::AddNode(const Station 
 
}
 

	
 
/**
 
 * Fill an edge with values from a link.
 
 * Fill an edge with values from a link. If usage < capacity set the usage,
 
 * otherwise set the restricted or unrestricted update timestamp.
 
 * @param to Destination node of the link.
 
 * @param capacity Capacity of the link.
 
 * @param usage Usage to be added or REFRESH_UNRESTRICTED or REFRESH_RESTRICTED.
 
 */
 
void LinkGraph::Node::AddEdge(NodeID to, uint capacity, uint usage)
 
{
 
@@ -188,17 +192,32 @@ void LinkGraph::Node::AddEdge(NodeID to,
 
	BaseEdge &edge = this->edges[to];
 
	BaseEdge &first = this->edges[this->index];
 
	edge.capacity = capacity;
 
	edge.usage = usage == UINT_MAX ? 0 : usage;
 
	edge.next_edge = first.next_edge;
 
	first.next_edge = to;
 
	edge.last_update = _date;
 
	switch (usage) {
 
		case REFRESH_UNRESTRICTED:
 
			edge.last_unrestricted_update = _date;
 
			break;
 
		case REFRESH_RESTRICTED:
 
			edge.last_restricted_update = _date;
 
			break;
 
		default:
 
			edge.usage = usage;
 
			break;
 
	}
 
}
 

	
 
/**
 
 * 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 or REFRESH_UNRESTRICTED or REFRESH_RESTRICTED.
 
 */
 
void LinkGraph::Node::UpdateEdge(NodeID to, uint capacity, uint usage)
 
{
 
	assert(capacity > 0);
 
	assert(usage <= capacity || usage == UINT_MAX);
 
	if (this->edges[to].last_update == INVALID_DATE) {
 
	assert(usage <= capacity || usage == REFRESH_RESTRICTED || usage == REFRESH_UNRESTRICTED);
 
	if (this->edges[to].capacity == 0) {
 
		this->AddEdge(to, capacity, usage);
 
	} else {
 
		(*this)[to].Update(capacity, usage);
 
@@ -214,7 +233,8 @@ void LinkGraph::Node::RemoveEdge(NodeID 
 
	if (this->index == to) return;
 
	BaseEdge &edge = this->edges[to];
 
	edge.capacity = 0;
 
	edge.last_update = INVALID_DATE;
 
	edge.last_unrestricted_update = INVALID_DATE;
 
	edge.last_restricted_update = INVALID_DATE;
 
	edge.usage = 0;
 

	
 
	NodeID prev = this->index;
 
@@ -233,24 +253,34 @@ void LinkGraph::Node::RemoveEdge(NodeID 
 
}
 

	
 
/**
 
 * Create a new edge or update an existing one. If usage is UINT_MAX refresh
 
 * the edge to have at least the given capacity, otherwise add the capacity.
 
 * Create a new edge or update an existing one. If usage is REFRESH_UNRESTRICTED
 
 * or REFRESH_RESTRICTED refresh the edge to have at least the given capacity
 
 * and also update the respective update timestamp, otherwise add the capacity.
 
 * @param from Start node of the edge.
 
 * @param to End node of the edge.
 
 * @param capacity Capacity to be added/updated.
 
 * @param usage Usage to be added or UINT_MAX.
 
 * @param usage Usage to be added or REFRESH_UNRESTRICTED or REFRESH_RESTRICTED.
 
 */
 
void LinkGraph::Edge::Update(uint capacity, uint usage)
 
{
 
	assert(this->edge.capacity > 0);
 
	if (usage == UINT_MAX) {
 
	if (usage > capacity) {
 
		this->edge.capacity = max(this->edge.capacity, capacity);
 
		switch (usage) {
 
			case REFRESH_UNRESTRICTED:
 
				this->edge.last_unrestricted_update = _date;
 
				break;
 
			case REFRESH_RESTRICTED:
 
				this->edge.last_restricted_update = _date;
 
				break;
 
			default:
 
				NOT_REACHED();
 
				break;
 
		}
 
	} else {
 
		assert(capacity >= usage);
 
		this->edge.capacity += capacity;
 
		this->edge.usage += usage;
 
	}
 
	this->edge.last_update = _date;
 
}
 

	
 
/**
src/linkgraph/linkgraph.h
Show inline comments
 
@@ -41,6 +41,22 @@ class LinkGraph : public LinkGraphPool::
 
public:
 

	
 
	/**
 
	 * Special modes for updating links. 'Restricted' means that vehicles with
 
	 * 'no loading' orders are serving the link. If a link is only served by
 
	 * such vehicles it's 'fully restricted'. This means the link can be used
 
	 * by cargo arriving in such vehicles, but not by cargo generated or
 
	 * transferring at the source station of the link. In order to find out
 
	 * about this condition we keep two update timestamps in each link, one for
 
	 * the restricted and one for the unrestricted part of it. If either one
 
	 * times out while the other is still valid the link becomes fully
 
	 * restricted or fully unrestricted, respectively.
 
	 */
 
	enum UpdateMode {
 
		REFRESH_RESTRICTED = UINT_MAX - 1, ///< Refresh restricted link.
 
		REFRESH_UNRESTRICTED = UINT_MAX    ///< Refresh unrestricted link.
 
	};
 

	
 
	/**
 
	 * 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.
 
@@ -60,11 +76,12 @@ public:
 
	 * the column as next_edge.
 
	 */
 
	struct BaseEdge {
 
		uint distance;    ///< Length of the link.
 
		uint capacity;    ///< Capacity of the link.
 
		uint usage;       ///< Usage of the link.
 
		Date last_update; ///< When the link was last updated.
 
		NodeID next_edge; ///< Destination of next valid edge starting at the same source node.
 
		uint distance;                 ///< Length of the link.
 
		uint capacity;                 ///< Capacity of the link.
 
		uint usage;                    ///< Usage of the link.
 
		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(uint distance = 0);
 
	};
 

	
 
@@ -104,10 +121,22 @@ public:
 
		uint Distance() const { return this->edge.distance; }
 

	
 
		/**
 
		 * Get edge's last update.
 
		 * Get the date of the last update to the edge's unrestricted capacity.
 
		 * @return Last update.
 
		 */
 
		Date LastUpdate() const { return this->edge.last_update; }
 
		Date LastUnrestrictedUpdate() const { return this->edge.last_unrestricted_update; }
 

	
 
		/**
 
		 * Get the date of the last update to the edge's restricted capacity.
 
		 * @return Last update.
 
		 */
 
		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 max(this->edge.last_unrestricted_update, this->edge.last_restricted_update); }
 
	};
 

	
 
	/**
 
@@ -285,6 +314,8 @@ public:
 
		 */
 
		Edge(BaseEdge &edge) : EdgeWrapper<BaseEdge>(edge) {}
 
		void Update(uint capacity, uint usage);
 
		void Restrict() { this->edge.last_unrestricted_update = INVALID_DATE; }
 
		void Release() { this->edge.last_restricted_update = INVALID_DATE; }
 
	};
 

	
 
	/**
src/saveload/linkgraph_sl.cpp
Show inline comments
 
@@ -118,12 +118,13 @@ static const SaveLoad _node_desc[] = {
 
 * SaveLoad desc for a link graph edge.
 
 */
 
static const SaveLoad _edge_desc[] = {
 
	SLE_VAR(Edge, distance,    SLE_UINT32),
 
	SLE_VAR(Edge, capacity,    SLE_UINT32),
 
	SLE_VAR(Edge, usage,       SLE_UINT32),
 
	SLE_VAR(Edge, last_update, SLE_INT32),
 
	SLE_VAR(Edge, next_edge,   SLE_UINT16),
 
	SLE_END()
 
	    SLE_VAR(Edge, distance,                 SLE_UINT32),
 
	    SLE_VAR(Edge, capacity,                 SLE_UINT32),
 
	    SLE_VAR(Edge, usage,                    SLE_UINT32),
 
	    SLE_VAR(Edge, last_unrestricted_update, SLE_INT32),
 
	SLE_CONDVAR(Edge, last_restricted_update,   SLE_INT32, 187, SL_MAX_VERSION),
 
	    SLE_VAR(Edge, next_edge,                SLE_UINT16),
 
	    SLE_END()
 
};
 

	
 
/**
src/station_cmd.cpp
Show inline comments
 
@@ -3417,13 +3417,18 @@ void DeleteStaleLinks(Station *from)
 
			Edge edge = it->second;
 
			Station *to = Station::Get((*lg)[it->first].Station());
 
			assert(to->goods[c].node == it->first);
 
			++it; // Do that before removing the node. Anything else may crash.
 
			++it; // Do that before removing the edge. Anything else may crash.
 
			assert(_date >= edge.LastUpdate());
 
			if ((uint)(_date - edge.LastUpdate()) > LinkGraph::MIN_TIMEOUT_DISTANCE +
 
					(DistanceManhattan(from->xy, to->xy) >> 2)) {
 
			uint timeout = LinkGraph::MIN_TIMEOUT_DISTANCE + (DistanceManhattan(from->xy, to->xy) >> 2);
 
			if ((uint)(_date - edge.LastUpdate()) > timeout) {
 
				node.RemoveEdge(to->goods[c].node);
 
				ge.flows.DeleteFlows(to->index);
 
				RerouteCargo(from, c, to->index, from->index);
 
			} else if (edge.LastUnrestrictedUpdate() != INVALID_DATE && (uint)(_date - edge.LastUnrestrictedUpdate()) > timeout) {
 
				edge.Restrict();
 
				RerouteCargo(from, c, to->index, from->index);
 
			} else if (edge.LastRestrictedUpdate() != INVALID_DATE && (uint)(_date - edge.LastRestrictedUpdate()) > timeout) {
 
				edge.Release();
 
			}
 
		}
 
		assert(_date >= lg->LastCompression());
src/vehicle.cpp
Show inline comments
 
@@ -50,6 +50,7 @@
 
#include "tunnel_map.h"
 
#include "depot_map.h"
 
#include "gamelog.h"
 
#include "linkgraph/linkgraph.h"
 

	
 
#include "table/strings.h"
 

	
 
@@ -2267,7 +2268,12 @@ uint Vehicle::RefreshNextHopsStats(Capac
 
					if (st != NULL && next_station != INVALID_STATION && next_station != st->index) {
 
						for (CapacitiesMap::const_iterator i = capacities.begin(); i != capacities.end(); ++i) {
 
							/* Refresh the link and give it a minimum capacity. */
 
							if (i->second > 0) IncreaseStats(st, i->first, next_station, i->second, UINT_MAX);
 
							if (i->second > 0) {
 
								/* A link is at least partly restricted if a
 
								 * vehicle can't load at its source. */
 
								IncreaseStats(st, i->first, next_station, i->second,
 
										(cur->GetLoadType() & OLFB_NO_LOAD) == 0 ? LinkGraph::REFRESH_UNRESTRICTED : LinkGraph::REFRESH_RESTRICTED);
 
							}
 
						}
 
					}
 
				}
0 comments (0 inline, 0 general)