cpp/openttd-patchpack/source Changeset - r28811:c7d0936f4cf0

Changeset - r28811:c7d0936f4cf0

Parent rev.

Child rev.

[Not reviewed]

master

0 7 0

Peter Nelson - 2 months ago 2024-02-25 12:36:13
peter1138@openttd.org

Change: Use bitmap for free unit ID generation. (#12165)

This improves performance of finding the next free unit number for a vehicle.

Based loosely on pool's used slot bitmap.

7 files changed with 70 insertions and 58 deletions:

src/company_base.h

src/economy.cpp

src/saveload/vehicle_sl.cpp

src/train_cmd.cpp

src/vehicle.cpp

src/vehicle_base.h

src/vehicle_cmd.cpp

0 comments (0 inline, 0 general)

src/company_base.h

➞

Show inline comments

@@ @@ -46,12 +46,25 @@ struct CompanyInfrastructure { @@
+	}
 	uint32_t GetRoadTotal() const;
 	uint32_t GetTramTotal() const;
 };
 class FreeUnitIDGenerator {
 public:
 	UnitID NextID() const;
 	UnitID UseID(UnitID index);
 	void ReleaseID(UnitID index);
 private:
 	using BitmapStorage = size_t;
 	static constexpr size_t BITMAP_SIZE = std::numeric_limits<BitmapStorage>::digits;
 	std::vector<BitmapStorage> used_bitmap;
 };
 typedef Pool<Company, CompanyID, 1, MAX_COMPANIES> CompanyPool;
 extern CompanyPool _company_pool;
 /** Statically loadable part of Company pool item */
 struct CompanyProperties {
 	uint32_t name_2;                   ///< Parameter of #name_1.
@@ @@ -126,12 +139,14 @@ struct Company : CompanyProperties, Comp @@
 	GroupStatistics group_all[VEH_COMPANY_END];      ///< NOSAVE: Statistics for the ALL_GROUP group.
 	GroupStatistics group_default[VEH_COMPANY_END];  ///< NOSAVE: Statistics for the DEFAULT_GROUP group.
 	CompanyInfrastructure infrastructure; ///< NOSAVE: Counts of company owned infrastructure.
 	FreeUnitIDGenerator freeunits[VEH_COMPANY_END];
 	Money GetMaxLoan() const;
 	/**
 	 * Is this company a valid company, controlled by the computer (a NoAI program)?
 	 * @param index Index in the pool.
 	 * @return \c true if it is a valid, computer controlled company, else \c false.

src/economy.cpp

➞

Show inline comments

@@ @@ -427,23 +427,19 @@ void ChangeOwnershipOfCompanyItems(Owner @@
 		for (Group *g : Group::Iterate()) {
 			if (g->owner == old_owner) g->owner = new_owner;
+		}
+	}
+	{
 		FreeUnitIDGenerator unitidgen[] = {
 			FreeUnitIDGenerator(VEH_TRAIN, new_owner), FreeUnitIDGenerator(VEH_ROAD,     new_owner),
 			FreeUnitIDGenerator(VEH_SHIP,  new_owner), FreeUnitIDGenerator(VEH_AIRCRAFT, new_owner)
 		};
 		Company *new_company = new_owner == INVALID_OWNER ? nullptr : Company::Get(new_owner);
 		/* Override company settings to new company defaults in case we need to convert them.
 		 * This is required as the CmdChangeServiceInt doesn't copy the supplied value when it is non-custom
 		 */
 		if (new_owner != INVALID_OWNER) {
 			Company *old_company = Company::Get(old_owner);
 			Company *new_company = Company::Get(new_owner);
 			old_company->settings.vehicle.servint_aircraft = new_company->settings.vehicle.servint_aircraft;
 			old_company->settings.vehicle.servint_trains = new_company->settings.vehicle.servint_trains;
 			old_company->settings.vehicle.servint_roadveh = new_company->settings.vehicle.servint_roadveh;
 			old_company->settings.vehicle.servint_ships = new_company->settings.vehicle.servint_ships;
 			old_company->settings.vehicle.servint_ispercent = new_company->settings.vehicle.servint_ispercent;
@@ @@ -454,14 +450,12 @@ void ChangeOwnershipOfCompanyItems(Owner @@
 				assert(new_owner != INVALID_OWNER);
 				/* Correct default values of interval settings while maintaining custom set ones.
 				 * This prevents invalid values on mismatching company defaults being accepted.
 				 */
 				if (!v->ServiceIntervalIsCustom()) {
 					Company *new_company = Company::Get(new_owner);
 					/* Technically, passing the interval is not needed as the command will query the default value itself.
 					 * However, do not rely on that behaviour.
 					 */
 					int interval = CompanyServiceInterval(new_company, v->type);
 					Command<CMD_CHANGE_SERVICE_INT>::Do(DC_EXEC | DC_BANKRUPT, v->index, interval, false, new_company->settings.vehicle.servint_ispercent);
+				}
@@ @@ -474,13 +468,14 @@ void ChangeOwnershipOfCompanyItems(Owner @@
 				if (v->IsEngineCountable()) {
 					GroupStatistics::CountEngine(v, 1);
+				}
 				if (v->IsPrimaryVehicle()) {
 					GroupStatistics::CountVehicle(v, 1);
 					v->unitnumber = unitidgen[v->type].NextID();
 					auto &unitidgen = new_company->freeunits[v->type];
 					v->unitnumber = unitidgen.UseID(unitidgen.NextID());
+				}
 				/* Invalidate the vehicle's cargo payment "owner cache". */
 				if (v->cargo_payment != nullptr) v->cargo_payment->owner = nullptr;
+			}
+		}

src/saveload/vehicle_sl.cpp

➞

Show inline comments

@@ @@ -514,12 +514,16 @@ void AfterLoadVehicles(bool part_of_load @@
 				break;
+			}
 			default: break;
+		}
 		if (part_of_load && v->unitnumber != 0) {
 			Company::Get(v->owner)->freeunits[v->type].UseID(v->unitnumber);
+		}
 		v->UpdateDeltaXY();
 		v->coord.left = INVALID_COORD;
 		v->sprite_cache.old_coord.left = INVALID_COORD;
 		v->UpdatePosition();
 		v->UpdateViewport(false);
+	}

src/train_cmd.cpp

➞

Show inline comments

@@ @@ -1175,13 +1175,13 @@ static void NormaliseTrainHead(Train *he @@
 	/* Update the refit button and window */
 	InvalidateWindowData(WC_VEHICLE_REFIT, head->index, VIWD_CONSIST_CHANGED);
 	SetWindowWidgetDirty(WC_VEHICLE_VIEW, head->index, WID_VV_REFIT);
 	/* If we don't have a unit number yet, set one. */
 	if (head->unitnumber != 0) return;
 	head->unitnumber = GetFreeUnitNumber(VEH_TRAIN);
+	head->unitnumber = Company::Get(head->owner)->freeunits[head->type].UseID(GetFreeUnitNumber(VEH_TRAIN));
+}
 /**
  * Move a rail vehicle around inside the depot.
  * @param flags type of operation
  *              Note: DC_AUTOREPLACE is set when autoreplace tries to undo its modifications or moves vehicles to temporary locations inside the depot.
@@ @@ -1333,12 +1333,13 @@ CommandCost CmdMoveRailVehicle(DoCommand @@
 				src_head->orders = src->orders;
 				if (src_head->orders != nullptr) src_head->AddToShared(src);
 				src_head->CopyVehicleConfigAndStatistics(src);
+			}
 			/* Remove stuff not valid anymore for non-front engines. */
 			DeleteVehicleOrders(src);
 			Company::Get(src->owner)->freeunits[src->type].ReleaseID(src->unitnumber);
 			src->unitnumber = 0;
 			src->name.clear();
+		}
 		/* We weren't a front engine but are becoming one. So
 		 * we should be put in the default group. */

src/vehicle.cpp

➞

Show inline comments

@@ @@ -843,12 +843,14 @@ void Vehicle::PreDestructor() @@
 		GroupStatistics::UpdateAutoreplace(this->owner);
 		if (this->owner == _local_company) InvalidateAutoreplaceWindow(this->engine_type, this->group_id);
 		DeleteGroupHighlightOfVehicle(this);
+	}
 	Company::Get(this->owner)->freeunits[this->type].ReleaseID(this->unitnumber);
 	if (this->type == VEH_AIRCRAFT && this->IsPrimaryVehicle()) {
 		Aircraft *a = Aircraft::From(this);
 		Station *st = GetTargetAirportIfValid(a);
 		if (st != nullptr) {
 			const AirportFTA *layout = st->airport.GetFTA()->layout;
 			CLRBITS(st->airport.flags, layout[a->previous_pos].block | layout[a->pos].block);
@@ @@ -1813,50 +1815,56 @@ Direction GetDirectionTowards(const Vehi @@
 VehicleEnterTileStatus VehicleEnterTile(Vehicle *v, TileIndex tile, int x, int y)
+{
 	return _tile_type_procs[GetTileType(tile)]->vehicle_enter_tile_proc(v, tile, x, y);
+}
 /**
  * Initializes the structure. Vehicle unit numbers are supposed not to change after
  * struct initialization, except after each call to this->NextID() the returned value
  * is assigned to a vehicle.
  * @param type type of vehicle
  * @param owner owner of vehicles
  * Find first unused unit number.
  * This does not mark the unit number as used.
  * @returns First unused unit number.
  */
-FreeUnitIDGenerator::FreeUnitIDGenerator(VehicleType type, CompanyID owner) : cache(nullptr), maxid(0), curid(0)
+UnitID FreeUnitIDGenerator::NextID() const
+{
 	/* Find maximum */
 	for (const Vehicle *v : Vehicle::Iterate()) {
 		if (v->type == type && v->owner == owner) {
 			this->maxid = std::max<UnitID>(this->maxid, v->unitnumber);
+		}
 	for (auto it = std::begin(this->used_bitmap); it != std::end(this->used_bitmap); ++it) {
 		BitmapStorage available = ~(*it);
 		if (available == 0) continue;
 		return static_cast<UnitID>(std::distance(std::begin(this->used_bitmap), it) * BITMAP_SIZE + FindFirstBit(available) + 1);
+	}
 	if (this->maxid == 0) return;
 	/* Reserving 'maxid + 2' because we need:
 	 * - space for the last item (with v->unitnumber == maxid)
 	 * - one free slot working as loop terminator in FreeUnitIDGenerator::NextID() */
 	this->cache = CallocT<bool>(this->maxid + 2);
 	/* Fill the cache */
 	for (const Vehicle *v : Vehicle::Iterate()) {
 		if (v->type == type && v->owner == owner) {
 			this->cache[v->unitnumber] = true;
+		}
+	}
 	return static_cast<UnitID>(this->used_bitmap.size() * BITMAP_SIZE + 1);
+}
 /** Returns next free UnitID. Supposes the last returned value was assigned to a vehicle. */
 UnitID FreeUnitIDGenerator::NextID()
 /**
  * Use a unit number. If the unit number is not valid it is ignored.
  * @param index Unit number to use.
  * @returns Unit number used.
  */
 UnitID FreeUnitIDGenerator::UseID(UnitID index)
+{
 	if (this->maxid <= this->curid) return ++this->curid;
 	while (this->cache[++this->curid]) { } // it will stop, we reserved more space than needed
 	return this->curid;
 	if (index == 0 || index == UINT16_MAX) return index;
 	index--;
 	size_t slot = index / BITMAP_SIZE;
 	if (slot >= this->used_bitmap.size()) this->used_bitmap.resize(slot + 1);
 	SetBit(this->used_bitmap[index / BITMAP_SIZE], index % BITMAP_SIZE);
 	return index + 1;
+}
 /**
  * Release a unit number. If the unit number is not valid it is ignored.
  * @param index Unit number to release.
  */
 void FreeUnitIDGenerator::ReleaseID(UnitID index)
+{
 	if (index == 0 || index == UINT16_MAX) return;
 	index--;
 	assert(index / BITMAP_SIZE < this->used_bitmap.size());
 	ClrBit(this->used_bitmap[index / BITMAP_SIZE], index % BITMAP_SIZE);
+}
 /**
  * Get an unused unit number for a vehicle (if allowed).
  * @param type Type of vehicle
  * @return A unused unit number for the given type of vehicle if it is allowed to build one, else \c UINT16_MAX.
@@ @@ -1873,15 +1881,13 @@ UnitID GetFreeUnitNumber(VehicleType typ @@
 		default: NOT_REACHED();
+	}
 	const Company *c = Company::Get(_current_company);
 	if (c->group_all[type].num_vehicle >= max_veh) return UINT16_MAX; // Currently already at the limit, no room to make a new one.
 	FreeUnitIDGenerator gen(type, _current_company);
 	return gen.NextID();
 	return c->freeunits[type].NextID();
+}
 /**
  * Check whether we can build infrastructure for the given
  * vehicle type. This to disable building stations etc. when

src/vehicle_base.h

➞

Show inline comments

@@ @@ -752,23 +752,25 @@ public: @@
 	/**
 	 * Copy certain configurations and statistics of a vehicle after successful autoreplace/renew
 	 * The function shall copy everything that cannot be copied by a command (like orders / group etc),
 	 * and that shall not be resetted for the new vehicle.
 	 * @param src The old vehicle
 	 */
-	inline void CopyVehicleConfigAndStatistics(const Vehicle *src)
 	inline void CopyVehicleConfigAndStatistics(Vehicle *src)
+	{
 		this->CopyConsistPropertiesFrom(src);
 		this->unitnumber = src->unitnumber;
 		this->current_order = src->current_order;
 		this->dest_tile  = src->dest_tile;
 		this->profit_this_year = src->profit_this_year;
 		this->profit_last_year = src->profit_last_year;
 		src->unitnumber = 0;
+	}
 	bool HandleBreakdown();
 	bool NeedsAutorenewing(const Company *c, bool use_renew_setting = true) const;
@@ @@ -1267,23 +1269,10 @@ struct SpecializedVehicle : public Vehic @@
 	 * @param from index of the first vehicle to consider
 	 * @return an iterable ensemble of all valid vehicles of type T
 	 */
 	static Pool::IterateWrapper<T> Iterate(size_t from = 0) { return Pool::IterateWrapper<T>(from); }
 };
 /** Generates sequence of free UnitID numbers */
 struct FreeUnitIDGenerator {
 	bool *cache;  ///< array of occupied unit id numbers
 	UnitID maxid; ///< maximum ID at the moment of constructor call
 	UnitID curid; ///< last ID returned; 0 if none
 	FreeUnitIDGenerator(VehicleType type, CompanyID owner);
 	UnitID NextID();
 	/** Releases allocated memory */
 	~FreeUnitIDGenerator() { free(this->cache); }
 };
 /** Sentinel for an invalid coordinate. */
 static const int32_t INVALID_COORD = 0x7fffffff;
 #endif /* VEHICLE_BASE_H */

src/vehicle_cmd.cpp

➞

Show inline comments

@@ @@ -191,12 +191,14 @@ std::tuple<CommandCost, VehicleID, uint, @@
 			GroupStatistics::UpdateAutoreplace(_current_company);
 			if (v->IsPrimaryVehicle()) {
 				GroupStatistics::CountVehicle(v, 1);
 				if (!(subflags & DC_AUTOREPLACE)) OrderBackup::Restore(v, client_id);
+			}
 			Company::Get(v->owner)->freeunits[v->type].UseID(v->unitnumber);
+		}
 		/* If we are not in DC_EXEC undo everything */
 		if (flags != subflags) {
 			Command<CMD_SELL_VEHICLE>::Do(DC_EXEC, v->index, false, false, INVALID_CLIENT_ID);

0 comments (0 inline, 0 general)