cpp/openttd-patchpack/source Changeset - r13218:a349a5df045c

Changeset - r13218:a349a5df045c

Parent rev.

Child rev.

[Not reviewed]

master

0 2 0

rubidium - 15 years ago 2009-10-07 08:25:12
rubidium@openttd.org

(svn r17735) -Codechange: update the cache one inserting/removing CargoPackets from the CargoList via Append/Truncate instead of rebuilding the whole cache. For Append this changes the O(n) cache rebuild into a O(1) cache update. For Truncate no temporary list is needed anymore (based on patch by fonsinchen)

2 files changed with 55 insertions and 25 deletions:

src/cargopacket.cpp

src/cargopacket.h

0 comments (0 inline, 0 general)

src/cargopacket.cpp

➞

Show inline comments

@@ @@ -73,12 +73,26 @@ CargoList::~CargoList() @@
 	while (!this->packets.empty()) {
 		delete this->packets.front();
 		this->packets.pop_front();
+	}
+}
 void CargoList::RemoveFromCache(const CargoPacket *cp)
+{
 	this->count                 -= cp->count;
 	this->feeder_share          -= cp->feeder_share;
 	this->cargo_days_in_transit -= cp->days_in_transit * cp->count;
+}
 void CargoList::AddToCache(const CargoPacket *cp)
+{
 	this->count                 += cp->count;
 	this->feeder_share          += cp->feeder_share;
 	this->cargo_days_in_transit += cp->days_in_transit * cp->count;
+}
 void CargoList::AgeCargo()
+{
 	for (List::const_iterator it = this->packets.begin(); it != this->packets.end(); it++) {
 		/* If we're at the maximum, then we can't increase no more. */
 		if ((*it)->days_in_transit == 0xFF) continue;
@@ @@ -89,49 +103,53 @@ void CargoList::AgeCargo() @@
 void CargoList::Append(CargoPacket *cp)
+{
 	assert(cp != NULL);
 	for (List::iterator it = this->packets.begin(); it != this->packets.end(); it++) {
 		if ((*it)->SameSource(cp) && (*it)->count + cp->count <= CargoPacket::MAX_COUNT) {
 			(*it)->count        += cp->count;
 			(*it)->feeder_share += cp->feeder_share;
 		CargoPacket *icp = *it;
 		if (icp->SameSource(cp) && icp->count + cp->count <= CargoPacket::MAX_COUNT) {
 			icp->count        += cp->count;
 			icp->feeder_share += cp->feeder_share;
 			this->AddToCache(cp);
 			delete cp;
 			this->InvalidateCache();
 			return;
+		}
+	}
 	/* The packet could not be merged with another one */
 	this->packets.push_back(cp);
-	this->InvalidateCache();
+	this->AddToCache(cp);
+}
-void CargoList::Truncate(uint count)
+void CargoList::Truncate(uint max_remaining)
+{
 	for (List::iterator it = this->packets.begin(); it != this->packets.end(); it++) {
 		uint local_count = (*it)->count;
 		if (local_count <= count) {
 			count -= local_count;
 	for (List::iterator it = packets.begin(); it != packets.end(); /* done during loop*/) {
 		CargoPacket *cp = *it;
 		if (max_remaining == 0) {
 			/* Nothing should remain, just remove the packets. */
 			packets.erase(it++);
 			this->RemoveFromCache(cp);
 			delete cp;
 			continue;
+		}
 		(*it)->count = count;
 		count = 0;
 		uint local_count = cp->count;
 		if (local_count > max_remaining) {
 			uint diff = local_count - max_remaining;
 			this->count -= diff;
 			this->cargo_days_in_transit -= cp->days_in_transit * diff;
 			cp->count = max_remaining;
 			max_remaining = 0;
 		} else {
 			max_remaining -= local_count;
+		}
 		++it;
+	}
 	while (!this->packets.empty()) {
 		CargoPacket *cp = this->packets.back();
 		if (cp->count != 0) break;
 		delete cp;
 		this->packets.pop_back();
+	}
 	this->InvalidateCache();
+}
 bool CargoList::MoveTo(CargoList *dest, uint count, CargoList::MoveToAction mta, CargoPayment *payment, uint data)
+{
 	assert(mta == MTA_FINAL_DELIVERY || dest != NULL);
 	assert(mta == MTA_UNLOAD || mta == MTA_CARGO_LOAD || payment != NULL);
@@ @@ -215,11 +233,9 @@ void CargoList::InvalidateCache() @@
+{
 	this->count = 0;
 	this->feeder_share = 0;
 	this->cargo_days_in_transit = 0;
 	for (List::const_iterator it = this->packets.begin(); it != this->packets.end(); it++) {
 		this->count                 += (*it)->count;
 		this->cargo_days_in_transit += (*it)->days_in_transit * (*it)->count;
 		this->feeder_share          += (*it)->feeder_share;
 		this->AddToCache(*it);
+	}
+}

src/cargopacket.h

➞

Show inline comments

@@ @@ -166,12 +166,26 @@ private: @@
 	Money feeder_share;         ///< Cache for the feeder share
 	uint count;                 ///< Cache for the number of cargo entities
 	uint cargo_days_in_transit; ///< Cache for the sum of number of days in transit of each entity; comparable to man-hours
 	List packets;               ///< The cargo packets in this list
 	/**
 	 * Update the cache to reflect adding of this packet.
 	 * Increases count, feeder share and days_in_transit
 	 * @param cp a new packet to be inserted
 	 */
 	void AddToCache(const CargoPacket *cp);
 	/**
 	 * Update the cached values to reflect the removal of this packet.
 	 * Decreases count, feeder share and days_in_transit
 	 * @param cp Packet to be removed from cache
 	 */
 	void RemoveFromCache(const CargoPacket *cp);
 public:
 	/** The stations, via GoodsEntry, have a CargoList. */
 	friend const struct SaveLoad *GetGoodsDesc();
 	/** The vehicles have a cargo list too. */
 	friend const SaveLoad *GetVehicleDescription(VehicleType vt);

0 comments (0 inline, 0 general)