/** Allocates a lot of vehicles and frees them again

 * @param vl pointer to an array of vehicles to get allocated. Can be NULL if the vehicles aren't needed (makes it test only)

 * @param num number of vehicles to allocate room for

 * @return true if there is room to allocate all the vehicles

 */

bool AllocateVehicles(Vehicle **vl, int num)

{

	int i;

	Vehicle *v;

	VehicleID counter = 0;

	for (i = 0; i != num; i++) {

		v = AllocateSingleVehicle(&counter);

		if (v == NULL) {

			return false;

		}

		if (vl != NULL) {

			vl[i] = v;

		}

	}

	return true;

}

/* 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)

{

	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 {

		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;

	new_hash = (x == INVALID_COORD) ? NULL : &_vehicle_position_hash[GEN_HASH(x, y)];

	old_hash = (old_x == INVALID_COORD) ? NULL : &_vehicle_position_hash[GEN_HASH(old_x, old_y)];

	if (old_hash == new_hash) return;

	/* 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;

		}

	}

	/* insert into hash table? */

	if (new_hash != NULL) {

		v->next_hash = *new_hash;

		*new_hash = v;

	}

}

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()

{

	uint i;

	/* Clean the vehicle pool, and reserve enough blocks

	 *  for the special vehicles, plus one for all the other

	 *  vehicles (which is increased on-the-fly) */

	CleanPool(&_Vehicle_pool);

	AddBlockToPool(&_Vehicle_pool);

	for (i = 0; i < BLOCKS_FOR_SPECIAL_VEHICLES; i++) {

		AddBlockToPool(&_Vehicle_pool);

	}

	ResetVehiclePosHash();

}