summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorsmatz <smatz@openttd.org>2009-06-09 17:20:06 +0000
committersmatz <smatz@openttd.org>2009-06-09 17:20:06 +0000
commit249b6e679843ff2ba2c11878f8fcf64024489820 (patch)
tree0e671f3b94d6ff66d6302140bc8b387228dabbd2 /src
parentea1a523a894acbabe26e36a46ab2348815677ec4 (diff)
downloadopenttd-249b6e679843ff2ba2c11878f8fcf64024489820.tar.xz
(svn r16544) -Codechange: use double-linked list for vehicle position caches in order to improve performance (~5% with many vehicles)
Diffstat (limited to 'src')
-rw-r--r--src/vehicle.cpp35
-rw-r--r--src/vehicle_base.h4
2 files changed, 10 insertions, 29 deletions
diff --git a/src/vehicle.cpp b/src/vehicle.cpp
index 8a1b649a6..c5c72f151 100644
--- a/src/vehicle.cpp
+++ b/src/vehicle.cpp
@@ -375,26 +375,16 @@ static void UpdateNewVehiclePosHash(Vehicle *v, bool remove)
/* Remove from the old position in the hash table */
if (old_hash != NULL) {
- Vehicle *last = NULL;
- Vehicle *u = *old_hash;
- while (u != v) {
- last = u;
- u = u->next_new_hash;
- assert(u != NULL);
- }
-
- if (last == NULL) {
- *old_hash = v->next_new_hash;
- } else {
- last->next_new_hash = v->next_new_hash;
- }
+ if (v->next_new_hash != NULL) v->next_new_hash->prev_new_hash = v->prev_new_hash;
+ *v->prev_new_hash = v->next_new_hash;
}
/* Insert vehicle at beginning of the new position in the hash table */
if (new_hash != NULL) {
v->next_new_hash = *new_hash;
+ if (v->next_new_hash != NULL) v->next_new_hash->prev_new_hash = &v->next_new_hash;
+ v->prev_new_hash = new_hash;
*new_hash = v;
- assert(v != v->next_new_hash);
}
/* Remember current hash position */
@@ -418,24 +408,15 @@ static void UpdateVehiclePosHash(Vehicle *v, int x, int y)
/* remove from hash table? */
if (old_hash != NULL) {
- Vehicle *last = NULL;
- Vehicle *u = *old_hash;
- while (u != v) {
- last = u;
- u = u->next_hash;
- assert(u != NULL);
- }
-
- if (last == NULL) {
- *old_hash = v->next_hash;
- } else {
- last->next_hash = v->next_hash;
- }
+ if (v->next_hash != NULL) v->next_hash->prev_hash = v->prev_hash;
+ *v->prev_hash = v->next_hash;
}
/* insert into hash table? */
if (new_hash != NULL) {
v->next_hash = *new_hash;
+ if (v->next_hash != NULL) v->next_hash->prev_hash = &v->next_hash;
+ v->prev_hash = new_hash;
*new_hash = v;
}
}
diff --git a/src/vehicle_base.h b/src/vehicle_base.h
index b5e7a16f5..795e48a71 100644
--- a/src/vehicle_base.h
+++ b/src/vehicle_base.h
@@ -100,8 +100,8 @@ public:
/* Boundaries for the current position in the world and a next hash link.
* NOSAVE: All of those can be updated with VehiclePositionChanged() */
Rect coord;
- Vehicle *next_hash;
- Vehicle *next_new_hash;
+ Vehicle *next_hash, **prev_hash;
+ Vehicle *next_new_hash, **prev_new_hash;
Vehicle **old_new_hash;
SpriteID colourmap; // NOSAVE: cached colour mapping