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

@@ @@ -49,6 +49,19 @@ struct CompanyInfrastructure { @@
 	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;
@@ @@ -129,6 +142,8 @@ struct Company : CompanyProperties, Comp @@
 	CompanyInfrastructure infrastructure; ///< NOSAVE: Counts of company owned infrastructure.
 	FreeUnitIDGenerator freeunits[VEH_COMPANY_END];
 	Money GetMaxLoan() const;
 	/**

src/economy.cpp

➞

Show inline comments

@@ @@ -430,17 +430,13 @@ void ChangeOwnershipOfCompanyItems(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;
@@ @@ -457,8 +453,6 @@ void ChangeOwnershipOfCompanyItems(Owner @@
 				 * 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.
 					 */
@@ @@ -477,7 +471,8 @@ void ChangeOwnershipOfCompanyItems(Owner @@
+				}
 				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". */

src/saveload/vehicle_sl.cpp

➞

Show inline comments

@@ @@ -517,6 +517,10 @@ void AfterLoadVehicles(bool part_of_load @@
 			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;

src/train_cmd.cpp

➞

Show inline comments

@@ @@ -1178,7 +1178,7 @@ static void NormaliseTrainHead(Train *he @@
 	/* 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));
+}
 /**
@@ @@ -1336,6 +1336,7 @@ CommandCost CmdMoveRailVehicle(DoCommand @@
+			}
 			/* 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();
+		}

src/vehicle.cpp

➞

Show inline comments

@@ @@ -846,6 +846,8 @@ void Vehicle::PreDestructor() @@
 		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);
@@ @@ -1816,44 +1818,50 @@ VehicleEnterTileStatus VehicleEnterTile( @@
+}
 /**
  * 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);
+}
 /**
@@ @@ -1876,9 +1884,7 @@ UnitID GetFreeUnitNumber(VehicleType typ @@
 	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();
+}

src/vehicle_base.h

➞

Show inline comments

@@ @@ -755,7 +755,7 @@ public: @@
 	 * 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);
@@ @@ -766,6 +766,8 @@ public: @@
 		this->profit_this_year = src->profit_this_year;
 		this->profit_last_year = src->profit_last_year;
 		src->unitnumber = 0;
+	}
@@ @@ -1270,19 +1272,6 @@ struct SpecializedVehicle : public Vehic @@
 	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;

src/vehicle_cmd.cpp

➞

Show inline comments

@@ @@ -194,6 +194,8 @@ std::tuple<CommandCost, VehicleID, uint, @@
 				GroupStatistics::CountVehicle(v, 1);
 				if (!(subflags & DC_AUTOREPLACE)) OrderBackup::Restore(v, client_id);
+			}
 			Company::Get(v->owner)->freeunits[v->type].UseID(v->unitnumber);
+		}

0 comments (0 inline, 0 general)