summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorrubidium <rubidium@openttd.org>2009-10-07 08:25:12 +0000
committerrubidium <rubidium@openttd.org>2009-10-07 08:25:12 +0000
commit705615fd914c51daacf4adb2aed9e21e6698e755 (patch)
tree3c4a711a5402700f16ace7ad4addc7b2e25502a5 /src
parent446363aac4c791cf39254c3da7f1bc34e2aebf57 (diff)
downloadopenttd-705615fd914c51daacf4adb2aed9e21e6698e755.tar.xz
(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)
Diffstat (limited to 'src')
-rw-r--r--src/cargopacket.cpp66
-rw-r--r--src/cargopacket.h14
2 files changed, 55 insertions, 25 deletions
diff --git a/src/cargopacket.cpp b/src/cargopacket.cpp
index e5a636bb4..829ef588f 100644
--- a/src/cargopacket.cpp
+++ b/src/cargopacket.cpp
@@ -76,6 +76,20 @@ CargoList::~CargoList()
}
}
+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++) {
@@ -92,43 +106,47 @@ 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;
- delete cp;
+ 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->InvalidateCache();
+ this->AddToCache(cp);
+ delete cp;
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;
- }
-
- while (!this->packets.empty()) {
- CargoPacket *cp = this->packets.back();
- if (cp->count != 0) break;
- delete cp;
- this->packets.pop_back();
+ 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;
}
-
- this->InvalidateCache();
}
bool CargoList::MoveTo(CargoList *dest, uint count, CargoList::MoveToAction mta, CargoPayment *payment, uint data)
@@ -218,8 +236,6 @@ void CargoList::InvalidateCache()
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);
}
}
diff --git a/src/cargopacket.h b/src/cargopacket.h
index bbad42bff..9d8251550 100644
--- a/src/cargopacket.h
+++ b/src/cargopacket.h
@@ -169,6 +169,20 @@ private:
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();