--- a/src/vehicle.cpp Wed Jun 13 12:05:56 2007 +0000
+++ b/src/vehicle.cpp Tue Jun 19 07:21:01 2007 +0000
@@ -43,7 +43,7 @@
#include "group.h"
#include "economy.h"
-#define INVALID_COORD (-0x8000)
+#define INVALID_COORD (0x7fffffff)
#define GEN_HASH(x, y) ((GB((y), 6, 6) << 6) + GB((x), 7, 6))
@@ -394,44 +394,117 @@
return true;
}
-
-static Vehicle *_vehicle_position_hash[0x1000];
+/* Size of the hash, 6 = 64 x 64, 7 = 128 x 128. Larger sizes will (in theory) reduce hash
+ * lookup times at the expense of memory usage. */
+const int HASH_BITS = 7;
+const int HASH_SIZE = 1 << HASH_BITS;
+const int HASH_MASK = HASH_SIZE - 1;
+const int TOTAL_HASH_SIZE = 1 << (HASH_BITS * 2);
+const int TOTAL_HASH_MASK = TOTAL_HASH_SIZE - 1;
+
+/* Resolution of the hash, 0 = 1*1 tile, 1 = 2*2 tiles, 2 = 4*4 tiles, etc.
+ * Profiling results show that 0 is fastest. */
+const int HASH_RES = 0;
+
+static Vehicle *_new_vehicle_position_hash[TOTAL_HASH_SIZE];
+
+static void *VehicleFromHash(int xl, int yl, int xu, int yu, void *data, VehicleFromPosProc *proc)
+{
+ for (int y = yl; ; y = (y + (1 << HASH_BITS)) & (HASH_MASK << HASH_BITS)) {
+ for (int x = xl; ; x = (x + 1) & HASH_MASK) {
+ Vehicle *v = _new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK];
+ for (; v != NULL; v = v->next_new_hash) {
+ void *a = proc(v, data);
+ if (a != NULL) return a;
+ }
+ if (x == xu) break;
+ }
+ if (y == yu) break;
+ }
+
+ return NULL;
+}
+
+
+void *VehicleFromPosXY(int x, int y, void *data, VehicleFromPosProc *proc)
+{
+ const int COLL_DIST = 6;
+
+ /* Hash area to scan is from xl,yl to xu,yu */
+ int xl = GB((x - COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS);
+ int xu = GB((x + COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS);
+ int yl = GB((y - COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS) << HASH_BITS;
+ int yu = GB((y + COLL_DIST) / TILE_SIZE, HASH_RES, HASH_BITS) << HASH_BITS;
+
+ return VehicleFromHash(xl, yl, xu, yu, data, proc);
+}
+
void *VehicleFromPos(TileIndex tile, void *data, VehicleFromPosProc *proc)
{
- Point pt = RemapCoords(TileX(tile) * TILE_SIZE, TileY(tile) * TILE_SIZE, 0);
-
- /* The hash area to scan */
- const int xl = GB(pt.x - 174, 7, 6);
- const int xu = GB(pt.x + 104, 7, 6);
- const int yl = GB(pt.y - 294, 6, 6) << 6;
- const int yu = GB(pt.y + 56, 6, 6) << 6;
-
- int x;
- int y;
-
- for (y = yl;; y = (y + (1 << 6)) & (0x3F << 6)) {
- for (x = xl;; x = (x + 1) & 0x3F) {
- Vehicle *v = _vehicle_position_hash[(x + y) & 0xFFFF];
-
- while (v != NULL) {
- void* a = proc(v, data);
-
- if (a != NULL) return a;
- v = v->next_hash;
- }
-
- if (x == xu) break;
- }
-
- if (y == yu) break;
+ int x = GB(TileX(tile), HASH_RES, HASH_BITS);
+ int y = GB(TileY(tile), HASH_RES, HASH_BITS) << HASH_BITS;
+
+ Vehicle *v = _new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK];
+ for (; v != NULL; v = v->next_new_hash) {
+ if (v->tile != tile) continue;
+
+ void *a = proc(v, data);
+ if (a != NULL) return a;
}
+
return NULL;
}
+static void UpdateNewVehiclePosHash(Vehicle *v, bool remove)
+{
+ Vehicle **old_hash = v->old_new_hash;
+ Vehicle **new_hash;
+
+ if (remove) {
+ new_hash = NULL;
+ } else {
+ int x = GB(TileX(v->tile), HASH_RES, HASH_BITS);
+ int y = GB(TileY(v->tile), HASH_RES, HASH_BITS) << HASH_BITS;
+ new_hash = &_new_vehicle_position_hash[(x + y) & TOTAL_HASH_MASK];
+ }
+
+ if (old_hash == new_hash) return;
+
+ /* 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;
+ }
+ }
+
+ /* Insert vehicle at beginning of the new position in the hash table */
+ if (new_hash != NULL) {
+ v->next_new_hash = *new_hash;
+ *new_hash = v;
+ assert(v != v->next_new_hash);
+ }
+
+ /* Remember current hash position */
+ v->old_new_hash = new_hash;
+}
+
+static Vehicle *_vehicle_position_hash[0x1000];
static void UpdateVehiclePosHash(Vehicle* v, int x, int y)
{
+ UpdateNewVehiclePosHash(v, x == INVALID_COORD);
+
Vehicle **old_hash, **new_hash;
int old_x = v->left_coord;
int old_y = v->top_coord;
@@ -467,7 +540,10 @@
void ResetVehiclePosHash()
{
+ Vehicle *v;
+ FOR_ALL_VEHICLES(v) { v->old_new_hash = NULL; }
memset(_vehicle_position_hash, 0, sizeof(_vehicle_position_hash));
+ memset(_new_vehicle_position_hash, 0, sizeof(_new_vehicle_position_hash));
}
void InitializeVehicles()
@@ -613,6 +689,7 @@
UpdateVehiclePosHash(v, INVALID_COORD, 0);
v->next_hash = NULL;
+ v->next_new_hash = NULL;
if (IsPlayerBuildableVehicleType(v)) DeleteVehicleOrders(v);
/* Now remove any artic part. This will trigger an other
@@ -768,9 +845,9 @@
* @param engine_type Which engine to refit
* @return Price for refitting
*/
-int32 GetRefitCost(EngineID engine_type)
+CommandCost GetRefitCost(EngineID engine_type)
{
- int32 base_cost = 0;
+ CommandCost base_cost = 0;
switch (GetEngine(engine_type)->type) {
case VEH_SHIP: base_cost = _eco->GetPrice(CEconomy::SHIP_BASE); break;
@@ -812,17 +889,29 @@
const int b = dpi->top + dpi->height;
/* The hash area to scan */
- const int xl = GB(l - 70, 7, 6);
- const int xu = GB(r, 7, 6);
- const int yl = GB(t - 70, 6, 6) << 6;
- const int yu = GB(b, 6, 6) << 6;
-
- int x;
- int y;
-
- for (y = yl;; y = (y + (1 << 6)) & (0x3F << 6)) {
- for (x = xl;; x = (x + 1) & 0x3F) {
- const Vehicle *v = _vehicle_position_hash[(x + y) & 0xFFFF];
+ int xl, xu, yl, yu;
+
+ if (dpi->width + 70 < (1 << (7 + 6))) {
+ xl = GB(l - 70, 7, 6);
+ xu = GB(r, 7, 6);
+ } else {
+ /* scan whole hash row */
+ xl = 0;
+ xu = 0x3F;
+ }
+
+ if (dpi->height + 70 < (1 << (6 + 6))) {
+ yl = GB(t - 70, 6, 6) << 6;
+ yu = GB(b, 6, 6) << 6;
+ } else {
+ /* scan whole column */
+ yl = 0;
+ yu = 0x3F << 6;
+ }
+
+ for (int y = yl;; y = (y + (1 << 6)) & (0x3F << 6)) {
+ for (int x = xl;; x = (x + 1) & 0x3F) {
+ const Vehicle *v = _vehicle_position_hash[x + y]; // already masked & 0xFFF
while (v != NULL) {
if (!(v->vehstatus & VS_HIDDEN) &&
@@ -1590,12 +1679,12 @@
* - bit 6 if set, then it's a vehicle list window, not a depot and Tile is ignored in this case
* - bit 8-11 Vehicle List Window type (ignored unless bit 1 is set)
*/
-int32 CmdMassStartStopVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
+CommandCost CmdMassStartStopVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
{
Vehicle **vl = NULL;
uint16 engine_list_length = 0;
uint16 engine_count = 0;
- int32 return_value = CMD_ERROR;
+ CommandCost return_value = CMD_ERROR;
uint i;
uint stop_command;
VehicleType vehicle_type = (VehicleType)GB(p2, 0, 5);
@@ -1622,7 +1711,7 @@
for (i = 0; i < engine_count; i++) {
const Vehicle *v = vl[i];
- int32 ret;
+ CommandCost ret;
if (!!(v->vehstatus & VS_STOPPED) != start_stop) continue;
@@ -1636,7 +1725,7 @@
ret = DoCommand(tile, v->index, 0, flags, stop_command);
- if (!CmdFailed(ret)) {
+ if (CmdSucceeded(ret)) {
return_value = 0;
/* We know that the command is valid for at least one vehicle.
* If we haven't set DC_EXEC, then there is no point in continueing because it will be valid */
@@ -1654,7 +1743,7 @@
* @param p1 Vehicle type
* @param p2 unused
*/
-int32 CmdDepotSellAllVehicles(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
+CommandCost CmdDepotSellAllVehicles(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
{
Vehicle **engines = NULL;
Vehicle **wagons = NULL;
@@ -1663,7 +1752,7 @@
uint16 wagon_list_length = 0;
uint16 wagon_count = 0;
- int32 cost = 0;
+ CommandCost cost = 0;
uint i, sell_command, total_number_vehicles;
VehicleType vehicle_type = (VehicleType)GB(p1, 0, 8);
@@ -1682,7 +1771,7 @@
total_number_vehicles = engine_count + wagon_count;
for (i = 0; i < total_number_vehicles; i++) {
const Vehicle *v;
- int32 ret;
+ CommandCost ret;
if (i < engine_count) {
v = engines[i];
@@ -1692,7 +1781,7 @@
ret = DoCommand(tile, v->index, 1, flags, sell_command);
- if (!CmdFailed(ret)) cost += ret;
+ if (CmdSucceeded(ret)) cost += ret;
}
free(engines);
@@ -1707,13 +1796,13 @@
* @param p1 Type of vehicle
* @param p2 Unused
*/
-int32 CmdDepotMassAutoReplace(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
+CommandCost CmdDepotMassAutoReplace(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
{
Vehicle **vl = NULL;
uint16 engine_list_length = 0;
uint16 engine_count = 0;
uint i, x = 0, y = 0, z = 0;
- int32 cost = 0;
+ CommandCost cost = 0;
VehicleType vehicle_type = (VehicleType)GB(p1, 0, 8);
if (!IsTileOwner(tile, _current_player)) return CMD_ERROR;
@@ -1725,7 +1814,7 @@
for (i = 0; i < engine_count; i++) {
Vehicle *v = vl[i];
bool stopped = !(v->vehstatus & VS_STOPPED);
- int32 ret;
+ CommandCost ret;
/* Ensure that the vehicle completely in the depot */
if (!IsVehicleInDepot(v)) continue;
@@ -1740,7 +1829,7 @@
}
ret = MaybeReplaceVehicle(v, !(flags & DC_EXEC), false);
- if (!CmdFailed(ret)) {
+ if (CmdSucceeded(ret)) {
cost += ret;
if (!(flags & DC_EXEC)) break;
/* There is a problem with autoreplace and newgrf
@@ -1773,11 +1862,11 @@
* @param p1 the original vehicle's index
* @param p2 1 = shared orders, else copied orders
*/
-int32 CmdCloneVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
+CommandCost CmdCloneVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
{
Vehicle *v_front, *v;
Vehicle *w_front, *w, *w_rear;
- int32 cost, total_cost = 0;
+ CommandCost cost, total_cost = 0;
uint32 build_argument = 2;
if (!IsValidVehicleID(p1)) return CMD_ERROR;
@@ -1837,7 +1926,7 @@
if (v->type == VEH_TRAIN && !IsFrontEngine(v)) {
/* this s a train car
* add this unit to the end of the train */
- int32 result = DoCommand(0, (w_rear->index << 16) | w->index, 1, flags, CMD_MOVE_RAIL_VEHICLE);
+ CommandCost result = DoCommand(0, (w_rear->index << 16) | w->index, 1, flags, CMD_MOVE_RAIL_VEHICLE);
if (CmdFailed(result)) {
/* The train can't be joined to make the same consist as the original.
* Sell what we already made (clean up) and return an error. */
@@ -1883,7 +1972,7 @@
if (w->cargo_type != v->cargo_type || w->cargo_subtype != v->cargo_type) {
cost = DoCommand(0, w->index, v->cargo_type | (v->cargo_subtype << 8) | 1U << 16 , flags, GetCmdRefitVeh(v));
- if (!CmdFailed(cost)) total_cost += cost;
+ if (CmdSucceeded(cost)) total_cost += cost;
}
if (w->type == VEH_TRAIN && EngineHasArticPart(w)) {
@@ -2134,7 +2223,7 @@
* @param vlw_flag tells what kind of list requested the goto depot
* @return 0 for success and CMD_ERROR if no vehicle is able to go to depot
*/
-int32 SendAllVehiclesToDepot(VehicleType type, uint32 flags, bool service, PlayerID owner, uint16 vlw_flag, uint32 id)
+CommandCost SendAllVehiclesToDepot(VehicleType type, uint32 flags, bool service, PlayerID owner, uint16 vlw_flag, uint32 id)
{
const Vehicle **sort_list = NULL;
uint n, i;
@@ -2145,13 +2234,13 @@
/* Send all the vehicles to a depot */
for (i = 0; i < n; i++) {
const Vehicle *v = sort_list[i];
- int32 ret = DoCommand(v->tile, v->index, (service ? 1 : 0) | DEPOT_DONT_CANCEL, flags, GetCmdSendToDepot(type));
+ CommandCost ret = DoCommand(v->tile, v->index, (service ? 1 : 0) | DEPOT_DONT_CANCEL, flags, GetCmdSendToDepot(type));
/* Return 0 if DC_EXEC is not set this is a valid goto depot command)
* In this case we know that at least one vehicle can be sent to a depot
* and we will issue the command. We can now safely quit the loop, knowing
* it will succeed at least once. With DC_EXEC we really need to send them to the depot */
- if (!CmdFailed(ret) && !(flags & DC_EXEC)) {
+ if (CmdSucceeded(ret) && !(flags & DC_EXEC)) {
free((void*)sort_list);
return 0;
}
@@ -2225,7 +2314,7 @@
v->current_order.flags = 0;
if (t.refit_cargo < NUM_CARGO) {
- int32 cost;
+ CommandCost cost;
_current_player = v->owner;
cost = DoCommand(v->tile, v->index, t.refit_cargo | t.refit_subtype << 8, DC_EXEC, GetCmdRefitVeh(v));
@@ -2273,7 +2362,7 @@
* @param p1 vehicle ID to name
* @param p2 unused
*/
-int32 CmdNameVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
+CommandCost CmdNameVehicle(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
{
Vehicle *v;
StringID str;
@@ -2307,7 +2396,7 @@
* @param p1 vehicle ID that is being service-interval-changed
* @param p2 new service interval
*/
-int32 CmdChangeServiceInt(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
+CommandCost CmdChangeServiceInt(TileIndex tile, uint32 flags, uint32 p1, uint32 p2)
{
Vehicle* v;
uint16 serv_int = GetServiceIntervalClamped(p2); /* Double check the service interval from the user-input */