Index: source/graphics/ObjectManager.cpp =================================================================== --- source/graphics/ObjectManager.cpp +++ source/graphics/ObjectManager.cpp @@ -29,7 +29,7 @@ #include "simulation2/Simulation2.h" #include "simulation2/components/ICmpTerrain.h" #include "simulation2/components/ICmpVisual.h" - +#include "simulation2/helpers/SparseFlatMap.h" bool CObjectManager::ObjectKey::operator< (const CObjectManager::ObjectKey& a) const { @@ -198,8 +198,8 @@ // rare occurrence of hotloading, so we'll tell the component (which does preserve the information) // to do the reloading itself const CSimulation2::InterfaceListUnordered& cmps = m_Simulation.GetEntitiesWithInterfaceUnordered(IID_Visual); - for (CSimulation2::InterfaceListUnordered::const_iterator eit = cmps.begin(); eit != cmps.end(); ++eit) - static_cast(eit->second)->Hotload(it->first); + for (const std::pair& entComp : cmps) + static_cast(entComp.second)->Hotload(it->first); } } Index: source/simulation2/Simulation2.h =================================================================== --- source/simulation2/Simulation2.h +++ source/simulation2/Simulation2.h @@ -25,8 +25,6 @@ #include "lib/file/vfs/vfs_path.h" -#include - #include class CSimulation2Impl; @@ -40,6 +38,9 @@ class CFrustum; class ScriptRuntime; +template +class DualFlatMap; + /** * Public API for simulation system. * Most code should interact with the simulation only through this API. @@ -207,7 +208,7 @@ void BroadcastMessage(const CMessage& msg) const; typedef std::vector > InterfaceList; - typedef boost::unordered_map InterfaceListUnordered; + typedef DualFlatMap InterfaceListUnordered; /** * Returns a list of components implementing the given interface, and their Index: source/simulation2/components/CCmpObstructionManager.cpp =================================================================== --- source/simulation2/components/CCmpObstructionManager.cpp +++ source/simulation2/components/CCmpObstructionManager.cpp @@ -27,6 +27,7 @@ #include "simulation2/helpers/Geometry.h" #include "simulation2/helpers/Rasterize.h" #include "simulation2/helpers/Render.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "simulation2/helpers/Spatial.h" #include "simulation2/serialization/SerializeTemplates.h" @@ -130,9 +131,11 @@ SpatialSubdivision m_UnitSubdivision; SpatialSubdivision m_StaticSubdivision; - // TODO: using std::map is a bit inefficient; is there a better way to store these? - std::map m_UnitShapes; - std::map m_StaticShapes; + template + using ShapeMap = SparseFlatMap; + + ShapeMap m_UnitShapes; + ShapeMap m_StaticShapes; u32 m_UnitShapeNext; // next allocated id u32 m_StaticShapeNext; @@ -184,8 +187,8 @@ serialize.NumberFixed_Unbounded("max clearance", m_MaxClearance); - SerializeMap()(serialize, "unit shapes", m_UnitShapes); - SerializeMap()(serialize, "static shapes", m_StaticShapes); + SerializeSparseFlatMap()(serialize, "unit shapes", m_UnitShapes); + SerializeSparseFlatMap()(serialize, "static shapes", m_StaticShapes); serialize.NumberU32_Unbounded("unit shape next", m_UnitShapeNext); serialize.NumberU32_Unbounded("static shape next", m_StaticShapeNext); @@ -261,18 +264,18 @@ m_UnitSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); m_StaticSubdivision.Reset(x1, z1, entity_pos_t::FromInt(8*TERRAIN_TILE_SIZE)); - for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) + for (const std::pair& item : m_UnitShapes) { - CFixedVector2D center(it->second.x, it->second.z); - CFixedVector2D halfSize(it->second.clearance, it->second.clearance); - m_UnitSubdivision.Add(it->first, center - halfSize, center + halfSize); + CFixedVector2D center(item.second.x, item.second.z); + CFixedVector2D halfSize(item.second.clearance, item.second.clearance); + m_UnitSubdivision.Add(item.first, center - halfSize, center + halfSize); } - for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) + for (const std::pair& item : m_StaticShapes) { - CFixedVector2D center(it->second.x, it->second.z); - CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(it->second.u, it->second.v, CFixedVector2D(it->second.hw, it->second.hh)); - m_StaticSubdivision.Add(it->first, center - bbHalfSize, center + bbHalfSize); + CFixedVector2D center(item.second.x, item.second.z); + CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(item.second.u, item.second.v, CFixedVector2D(item.second.hw, item.second.hh)); + m_StaticSubdivision.Add(item.first, center - bbHalfSize, center + bbHalfSize); } } @@ -280,7 +283,7 @@ { UnitShape shape = { ent, x, z, clearance, flags, group }; u32 id = m_UnitShapeNext++; - m_UnitShapes[id] = shape; + m_UnitShapes.insert_or_assign(id, shape); m_UnitSubdivision.Add(id, CFixedVector2D(x - clearance, z - clearance), CFixedVector2D(x + clearance, z + clearance)); @@ -298,7 +301,7 @@ StaticShape shape = { ent, x, z, u, v, w/2, h/2, flags, group, group2 }; u32 id = m_StaticShapeNext++; - m_StaticShapes[id] = shape; + m_StaticShapes.insert_or_assign(id, shape); CFixedVector2D center(x, z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(u, v, CFixedVector2D(w/2, h/2)); @@ -334,7 +337,7 @@ if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + UnitShape& shape = m_UnitShapes.at(TAG_TO_INDEX(tag)); MakeDirtyUnit(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region @@ -356,7 +359,7 @@ CFixedVector2D u(c, -s); CFixedVector2D v(s, c); - StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + StaticShape& shape = m_StaticShapes.at(TAG_TO_INDEX(tag)); MakeDirtyStatic(shape.flags, TAG_TO_INDEX(tag), shape); // dirty the old shape region @@ -383,7 +386,7 @@ if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + UnitShape& shape = m_UnitShapes.at(TAG_TO_INDEX(tag)); if (moving) shape.flags |= FLAG_MOVING; else @@ -399,7 +402,7 @@ if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + UnitShape& shape = m_UnitShapes.at(TAG_TO_INDEX(tag)); shape.group = group; } } @@ -410,7 +413,7 @@ if (TAG_IS_STATIC(tag)) { - StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + StaticShape& shape = m_StaticShapes.at(TAG_TO_INDEX(tag)); shape.group = group; shape.group2 = group2; } @@ -422,7 +425,7 @@ if (TAG_IS_UNIT(tag)) { - UnitShape& shape = m_UnitShapes[TAG_TO_INDEX(tag)]; + UnitShape& shape = m_UnitShapes.at(TAG_TO_INDEX(tag)); m_UnitSubdivision.Remove(TAG_TO_INDEX(tag), CFixedVector2D(shape.x - shape.clearance, shape.z - shape.clearance), CFixedVector2D(shape.x + shape.clearance, shape.z + shape.clearance)); @@ -433,7 +436,7 @@ } else { - StaticShape& shape = m_StaticShapes[TAG_TO_INDEX(tag)]; + StaticShape& shape = m_StaticShapes.at(TAG_TO_INDEX(tag)); CFixedVector2D center(shape.x, shape.z); CFixedVector2D bbHalfSize = Geometry::GetHalfBoundingBox(shape.u, shape.v, CFixedVector2D(shape.hw, shape.hh)); @@ -873,7 +876,7 @@ m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); for (const entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); + ShapeMap::const_iterator it = m_UnitShapes.find(shape); ENSURE(it != m_UnitShapes.end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) @@ -889,7 +892,7 @@ m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); for (const entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); + ShapeMap::const_iterator it = m_StaticShapes.find(shape); ENSURE(it != m_StaticShapes.end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) @@ -941,7 +944,7 @@ m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); for (entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); + ShapeMap::const_iterator it = m_UnitShapes.find(shape); ENSURE(it != m_UnitShapes.end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) @@ -962,7 +965,7 @@ m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); for (entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); + ShapeMap::const_iterator it = m_StaticShapes.find(shape); ENSURE(it != m_StaticShapes.end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) @@ -1008,7 +1011,7 @@ m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); for (const entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); + ShapeMap::const_iterator it = m_UnitShapes.find(shape); ENSURE(it != m_UnitShapes.end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) @@ -1033,7 +1036,7 @@ m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); for (const entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); + ShapeMap::const_iterator it = m_StaticShapes.find(shape); ENSURE(it != m_StaticShapes.end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) @@ -1162,7 +1165,7 @@ m_UnitSubdivision.GetInRange(unitShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); for (entity_id_t& unitShape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(unitShape); + ShapeMap::const_iterator it = m_UnitShapes.find(unitShape); ENSURE(it != m_UnitShapes.end()); if (!filter.TestShape(UNIT_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, INVALID_ENTITY)) @@ -1190,7 +1193,7 @@ m_StaticSubdivision.GetInRange(staticShapes, CFixedVector2D(x0, z0), CFixedVector2D(x1, z1)); for (entity_id_t& staticShape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(staticShape); + ShapeMap::const_iterator it = m_StaticShapes.find(staticShape); ENSURE(it != m_StaticShapes.end()); if (!filter.TestShape(STATIC_INDEX_TO_TAG(it->first), it->second.flags, it->second.group, it->second.group2)) @@ -1227,7 +1230,7 @@ for (const u32& unitShape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(unitShape); + ShapeMap::const_iterator it = m_UnitShapes.find(unitShape); ENSURE(it != m_UnitShapes.end()); const UnitShape& shape = it->second; @@ -1280,7 +1283,7 @@ for (const u32& staticShape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(staticShape); + ShapeMap::const_iterator it = m_StaticShapes.find(staticShape); ENSURE(it != m_StaticShapes.end()); const StaticShape& shape = it->second; @@ -1324,19 +1327,19 @@ (m_WorldX1-m_WorldX0).ToFloat(), (m_WorldZ1-m_WorldZ0).ToFloat(), 0, m_DebugOverlayLines.back(), true); - for (std::map::iterator it = m_UnitShapes.begin(); it != m_UnitShapes.end(); ++it) + for (const std::pair& item : m_UnitShapes) { m_DebugOverlayLines.push_back(SOverlayLine()); - m_DebugOverlayLines.back().m_Color = ((it->second.flags & FLAG_MOVING) ? movingColor : defaultColor); - SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.clearance.ToFloat(), it->second.clearance.ToFloat(), 0, m_DebugOverlayLines.back(), true); + m_DebugOverlayLines.back().m_Color = ((item.second.flags & FLAG_MOVING) ? movingColor : defaultColor); + SimRender::ConstructSquareOnGround(GetSimContext(), item.second.x.ToFloat(), item.second.z.ToFloat(), item.second.clearance.ToFloat(), item.second.clearance.ToFloat(), 0, m_DebugOverlayLines.back(), true); } - for (std::map::iterator it = m_StaticShapes.begin(); it != m_StaticShapes.end(); ++it) + for (const std::pair& item : m_StaticShapes) { m_DebugOverlayLines.push_back(SOverlayLine()); m_DebugOverlayLines.back().m_Color = defaultColor; - float a = atan2f(it->second.v.X.ToFloat(), it->second.v.Y.ToFloat()); - SimRender::ConstructSquareOnGround(GetSimContext(), it->second.x.ToFloat(), it->second.z.ToFloat(), it->second.hw.ToFloat()*2, it->second.hh.ToFloat()*2, a, m_DebugOverlayLines.back(), true); + float a = atan2f(item.second.v.X.ToFloat(), item.second.v.Y.ToFloat()); + SimRender::ConstructSquareOnGround(GetSimContext(), item.second.x.ToFloat(), item.second.z.ToFloat(), item.second.hw.ToFloat()*2, item.second.hh.ToFloat()*2, a, m_DebugOverlayLines.back(), true); } m_DebugOverlayDirty = false; Index: source/simulation2/components/CCmpRangeManager.cpp =================================================================== --- source/simulation2/components/CCmpRangeManager.cpp +++ source/simulation2/components/CCmpRangeManager.cpp @@ -21,7 +21,6 @@ #include "ICmpRangeManager.h" #include "ICmpTerrain.h" -#include "simulation2/system/EntityMap.h" #include "simulation2/MessageTypes.h" #include "simulation2/components/ICmpFogging.h" #include "simulation2/components/ICmpMirage.h" @@ -34,6 +33,7 @@ #include "simulation2/components/ICmpWaterManager.h" #include "simulation2/helpers/MapEdgeTiles.h" #include "simulation2/helpers/Render.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "simulation2/helpers/Spatial.h" #include "graphics/Overlay.h" @@ -293,6 +293,9 @@ } }; +using EntityMap = SparseFlatMap; +using EntityIdDataPair = EntityMap::value_type; + /** * Functor for sorting entities by distance from a source point. * It must only be passed entities that are in 'entities' @@ -300,7 +303,7 @@ */ struct EntityDistanceOrdering { - EntityDistanceOrdering(const EntityMap& entities, const CFixedVector2D& source) : + EntityDistanceOrdering(const EntityMap& entities, const CFixedVector2D& source) : m_EntityData(entities), m_Source(source) { } @@ -314,7 +317,7 @@ return (vecA.CompareLength(vecB) < 0); } - const EntityMap& m_EntityData; + const EntityMap& m_EntityData; CFixedVector2D m_Source; private: @@ -366,7 +369,7 @@ // Range query state: tag_t m_QueryNext; // next allocated id std::map m_Queries; - EntityMap m_EntityData; + EntityMap m_EntityData; FastSpatialSubdivision m_Subdivision; // spatial index of m_EntityData std::vector m_SubdivisionResults; @@ -459,7 +462,7 @@ serialize.NumberU32_Unbounded("query next", m_QueryNext); SerializeMap()(serialize, "queries", m_Queries, GetSimContext()); - SerializeEntityMap()(serialize, "entity data", m_EntityData); + SerializeSparseFlatMap()(serialize, "entity data", m_EntityData); SerializeVector()(serialize, "los reveal all", m_LosRevealAll); serialize.Bool("los circular", m_LosCircular); @@ -540,7 +543,7 @@ entdata.size = cmpObstruction->GetSize().ToInt_RoundToInfinity(); // Remember this entity - m_EntityData.insert(ent, entdata); + m_EntityData.insert_or_assign(ent, entdata); break; } case MT_PositionChanged: @@ -548,7 +551,7 @@ const CMessagePositionChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -615,7 +618,7 @@ const CMessageOwnershipChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -649,7 +652,7 @@ const CMessageDestroy& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -674,7 +677,7 @@ const CMessageVisionRangeChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -714,7 +717,7 @@ const CMessageVisionSharingChanged& msgData = static_cast (msg); entity_id_t ent = msgData.entity; - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // Ignore if we're not already tracking this entity if (it == m_EntityData.end()) @@ -863,17 +866,17 @@ m_LosTiles.clear(); m_LosTiles.resize(m_LosTilesPerSide*m_LosTilesPerSide); - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) - if (it->second.HasFlag()) + for (const EntityIdDataPair& data : m_EntityData) + if (data.second.HasFlag()) { - if (it->second.HasFlag()) - SharingLosAdd(it->second.visionSharing, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z)); + if (data.second.HasFlag()) + SharingLosAdd(data.second.visionSharing, data.second.visionRange, CFixedVector2D(data.second.x, data.second.z)); else - LosAdd(it->second.owner, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z)); - AddToTile(PosToLosTilesHelper(it->second.x, it->second.z), it->first); + LosAdd(data.second.owner, data.second.visionRange, CFixedVector2D(data.second.x, data.second.z)); + AddToTile(PosToLosTilesHelper(data.second.x, data.second.z), data.first); - if (it->second.HasFlag()) - RevealShore(it->second.owner, true); + if (data.second.HasFlag()) + RevealShore(data.second.owner, true); } m_TotalInworldVertices = 0; @@ -894,9 +897,9 @@ { m_Subdivision.Reset(x1, z1); - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) - if (it->second.HasFlag()) - m_Subdivision.Add(it->first, CFixedVector2D(it->second.x, it->second.z), it->second.size); + for (const EntityIdDataPair& data : m_EntityData) + if (data.second.HasFlag()) + m_Subdivision.Add(data.first, CFixedVector2D(data.second.x, data.second.z), data.second.size); } virtual tag_t CreateActiveQuery(entity_id_t source, @@ -1063,11 +1066,11 @@ { std::vector entities; - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (const EntityIdDataPair& data : m_EntityData) { // Check owner and add to list if it matches - if (CalcOwnerMask(it->second.owner) & ownerMask) - entities.push_back(it->first); + if (CalcOwnerMask(data.second.owner) & ownerMask) + entities.push_back(data.first); } return entities; @@ -1176,12 +1179,12 @@ // Special case: range -1.0 means check all entities ignoring distance if (q.maxRange == entity_pos_t::FromInt(-1)) { - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (const EntityIdDataPair& data : m_EntityData) { - if (!TestEntityQuery(q, it->first, it->second)) + if (!TestEntityQuery(q, data.first, data.second)) continue; - r.push_back(it->first); + r.push_back(data.first); } } // Not the entire world, so check a parabolic range, or a regular range @@ -1197,7 +1200,7 @@ for (size_t i = 0; i < m_SubdivisionResults.size(); ++i) { - EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); + EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); ENSURE(it != m_EntityData.end()); if (!TestEntityQuery(q, it->first, it->second)) @@ -1235,7 +1238,7 @@ for (size_t i = 0; i < m_SubdivisionResults.size(); ++i) { - EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); + EntityMap::const_iterator it = m_EntityData.find(m_SubdivisionResults[i]); ENSURE(it != m_EntityData.end()); if (!TestEntityQuery(q, it->first, it->second)) @@ -1551,7 +1554,7 @@ virtual void SetEntityFlag(entity_id_t ent, const std::string& identifier, bool value) { - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); // We don't have this entity if (it == m_EntityData.end()) @@ -1579,7 +1582,7 @@ virtual void ActivateScriptedVisibility(entity_id_t ent, bool status) { - EntityMap::iterator it = m_EntityData.find(ent); + EntityMap::iterator it = m_EntityData.find(ent); if (it != m_EntityData.end()) it->second.SetFlag(status); } @@ -1617,7 +1620,7 @@ CmpPtr cmpVisibility(ent); // Possibly ask the scripted Visibility component - EntityMap::const_iterator it = m_EntityData.find(ent.GetId()); + EntityMap::const_iterator it = m_EntityData.find(ent.GetId()); if (it != m_EntityData.end()) { if (it->second.HasFlag() && cmpVisibility) @@ -1713,7 +1716,7 @@ if (std::find(m_ModifiedEntities.begin(), m_ModifiedEntities.end(), entId) != m_ModifiedEntities.end()) return ComputeLosVisibility(ent, player); - EntityMap::const_iterator it = m_EntityData.find(entId); + EntityMap::const_iterator it = m_EntityData.find(entId); if (it == m_EntityData.end()) return ComputeLosVisibility(ent, player); @@ -1791,7 +1794,7 @@ void UpdateVisibility(entity_id_t ent, player_id_t player) { - EntityMap::iterator itEnts = m_EntityData.find(ent); + EntityMap::iterator itEnts = m_EntityData.find(ent); if (itEnts == m_EntityData.end()) return; @@ -1957,9 +1960,9 @@ // So we just remember what entities to mirage and do that later. std::vector miragableEntities; - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (const EntityIdDataPair& data : m_EntityData) { - CmpPtr cmpPosition(GetSimContext(), it->first); + CmpPtr cmpPosition(GetSimContext(), data.first); if (!cmpPosition || !cmpPosition->IsInWorld()) continue; @@ -1971,9 +1974,9 @@ if (!los.IsExplored(i,j) || los.IsVisible(i,j)) continue; - CmpPtr cmpFogging(GetSimContext(), it->first); + CmpPtr cmpFogging(GetSimContext(), data.first); if (cmpFogging) - miragableEntities.push_back(it->first); + miragableEntities.push_back(data.first); } for (std::vector::iterator it = miragableEntities.begin(); it != miragableEntities.end(); ++it) Index: source/simulation2/helpers/Selection.cpp =================================================================== --- source/simulation2/helpers/Selection.cpp +++ source/simulation2/helpers/Selection.cpp @@ -160,10 +160,10 @@ else // owner == INVALID_PLAYER; Used when selecting units in Atlas or other mods that allow all kinds of selectables to be selected. { const CSimulation2::InterfaceListUnordered& selectableEnts = simulation.GetEntitiesWithInterfaceUnordered(IID_Selectable); - for (CSimulation2::InterfaceListUnordered::const_iterator it = selectableEnts.begin(); it != selectableEnts.end(); ++it) + for (const std::pair& entComp : selectableEnts) { - if (CheckEntityVisibleAndInRect(it->second->GetEntityHandle(), cmpRangeManager, camera, sx0, sy0, sx1, sy1, owner, allowEditorSelectables)) - hitEnts.push_back(it->first); + if (CheckEntityVisibleAndInRect(entComp.second->GetEntityHandle(), cmpRangeManager, camera, sx0, sy0, sx1, sy1, owner, allowEditorSelectables)) + hitEnts.push_back(entComp.first); } } @@ -204,13 +204,13 @@ std::vector hitEnts; const CSimulation2::InterfaceListUnordered& ents = simulation.GetEntitiesWithInterfaceUnordered(IID_Selectable); - for (CSimulation2::InterfaceListUnordered::const_iterator it = ents.begin(); it != ents.end(); ++it) + for (const std::pair& entComp : ents) { - entity_id_t ent = it->first; - CEntityHandle handle = it->second->GetEntityHandle(); + entity_id_t ent = entComp.first; + CEntityHandle handle = entComp.second->GetEntityHandle(); // Check if this entity is only selectable in Atlas - if (static_cast(it->second)->IsEditorOnly() && !allowEditorSelectables) + if (static_cast(entComp.second)->IsEditorOnly() && !allowEditorSelectables) continue; if (matchRank) Index: source/simulation2/helpers/SparseFlatMap.h =================================================================== --- /dev/null +++ source/simulation2/helpers/SparseFlatMap.h @@ -0,0 +1,355 @@ +/* Copyright (C) 2019 Wildfire Games. + * This file is part of 0 A.D. + * + * 0 A.D. is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 2 of the License, or + * (at your option) any later version. + * + * 0 A.D. is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with 0 A.D. If not, see . + */ + +#ifndef INCLUDED_SparseFlatMap +#define INCLUDED_SparseFlatMap + +#include "simulation2/serialization/ISerializer.h" +#include "simulation2/serialization/IDeserializer.h" + +#include +#include + +/** + * SparseFlatMap is a faster replacement for std::map and std::unordered_map. + * Requirements of T: T can be used as an array index. + * Requirements of V: movable + * Other requirements: + * - the iteration order must be deterministic to ensure network synchronicity and replays. + * + * The basic principle is to have a sparse vector of + * and a dense "data" vector of . + * + * Inserting is slightly slower than a vector because of the pointer book-keeping and the key storage. + * Erasing just sets the key to nullptr and swap-and-erases the data, to keep it dense. + * It's thus also slightly slower than a vector. + * Iteration happens over the dense data deque, so it's as fast as iterating a deque (really fast). + * Random Access means two dereferences, so in theory it's about as fast as a deque, which is is still really fast. + */ + +template +class SparseFlatMapCore +{ +private: + friend class TestSparseFlatMap; + +public: + + using key_type = T; + using mapped_type = V; + using value_type = std::pair; + +protected: + using data_value_type = std::pair; + using keys_value_type = data_value_type*; + + using keys_container = std::vector; + keys_container m_Keys; + + // The data container is a deque since that avoids moving items when the buffer has to grow + // which avoids additional book-keeping when that needs to happen, + // and it's only slightly slower than a vector for the regular case. + using data_container = std::deque; + data_container m_Data; + + Map* self() { return static_cast(this); } + + const Map* self() const { return static_cast(this); } + + static key_type Idx(const key_type key) { return key; } + + const keys_container& Keys(const key_type) const { return m_Keys; } + keys_container& Keys(const key_type) { return m_Keys; } + +public: + + SparseFlatMapCore() + { + m_Keys.reserve(4096); + }; + + SparseFlatMapCore(const SparseFlatMapCore& o) + { + m_Keys = o.m_Keys; + std::copy(o.m_Data.begin(), o.m_Data.end(), std::inserter(m_Data, m_Data.begin())); + static_cast(this)->copy(*o.self()); + } + + SparseFlatMapCore& operator=(const SparseFlatMapCore& o) + { + SparseFlatMapCore tmp(o); + m_Data.swap(tmp.m_Data); + m_Keys.swap(tmp.m_Keys); + static_cast(this)->swap(*tmp.self()); + return *this; + } + + // Provide an iterator-like interface for find() and such + // only this type cannot actually iterate. + template + class pseudo_iterator + { + friend class SparseFlatMapCore; + K key; + M* value; + + pseudo_iterator(K k, M* v) : key(k), value(v) {}; + // Fake for comparison with end() + pseudo_iterator(const typename data_container::iterator&) : key(0), value(nullptr) {}; + pseudo_iterator(const typename data_container::const_iterator&) : key(0), value(nullptr) {}; + + template + struct proxy + { + U ptr; + proxy(U p) : ptr(p) {}; + U* operator->() { return &ptr; } + const U* operator->() const { return &ptr; } + }; + + public: + pseudo_iterator(const pseudo_iterator::type>& o) : key(o.key), value(o.value) {}; + pseudo_iterator(const pseudo_iterator& o) : key(o.key), value(o.value) {}; + + proxy> operator->() { return proxy>((*this).operator*()); } + std::pair operator*() { return std::make_pair(key, std::reference_wrapper(*value)); } + const proxy> operator->() const { return proxy>((*this).operator*()); } + const std::pair operator*() const { return std::make_pair(key, std::reference_wrapper(*value)); } + + bool operator==(const pseudo_iterator& it) const { return value == it.value; }; + bool operator!=(const pseudo_iterator& it) const { return value != it.value; }; + bool operator==(const typename data_container::iterator&) const { return value == nullptr; }; + bool operator!=(const typename data_container::iterator&) const { return value != nullptr; }; + bool operator==(const typename data_container::const_iterator&) const { return value == nullptr; }; + bool operator!=(const typename data_container::const_iterator&) const { return value != nullptr; }; + }; + + typedef pseudo_iterator iterator; + typedef const pseudo_iterator const_iterator; + + iterator it(const key_type& key) + { + return iterator(key, &(self()->Keys(key)[Map::Idx(key)]->second)); + } + + const_iterator it(const key_type& key) const + { + return const_iterator(key, &(self()->Keys(key)[Map::Idx(key)]->second)); + } + + // begin() and end() return data_container's iterator as we iterate over the compact data directly for efficiently. + typename data_container::iterator begin() { return m_Data.begin(); } + typename data_container::iterator end() { return m_Data.end(); } + typename data_container::const_iterator begin() const { return m_Data.begin(); } + typename data_container::const_iterator end() const { return m_Data.end(); } + + bool empty() const { return m_Data.empty(); } + size_t size() const { return m_Data.size(); } + + std::pair insert_or_assign(const key_type& key, const mapped_type& value) + { + key_type idx = Map::Idx(key); + auto& keys = self()->Keys(key); + + if (static_cast(idx) >= keys.size()) + keys.resize(idx + 1, { nullptr }); + + bool inserted = false; + if (keys[idx] == nullptr) + { + inserted = true; + m_Data.push_back({ key, value }); + keys[idx] = { &m_Data.back() }; + } + else + *(keys[idx]) = { key, value }; + return { it(key), inserted }; + } + + size_t erase(const iterator& it) + { + return erase(it->first); + } + + size_t erase(const key_type& key) + { + key_type idx = Map::Idx(key); + keys_container& keys = self()->Keys(key); + if (static_cast(idx) >= keys.size() || keys[idx] == nullptr) + return 0; + + data_value_type& data = *(keys[idx]); + data.second.~V(); + if (&data != &m_Data.back()) + { + data = std::move(m_Data.back()); + self()->Keys(data.first)[Map::Idx(data.first)] = &data; + } + m_Data.pop_back(); + + keys[idx] = nullptr; + return 1; + } + + void clear() + { + m_Keys.clear(); + m_Data.clear(); + + self()->clearKeys(); + } + + mapped_type& operator[](const key_type& k) + { + iterator it = find(k); + if (find(k) == end()) + return insert_or_assign(k, {}).first->second; + return it->second; + } + + mapped_type& at(const key_type& k) + { + ENSURE(find(k) != end()); + return (*find(k)).second; + } + + const mapped_type& at(const key_type& k) const + { + ENSURE(find(k) != end()); + return (*find(k)).second; + } + + iterator find(const key_type& key) + { + key_type idx = Map::Idx(key); + if (static_cast(idx) < self()->Keys(key).size() && self()->Keys(key)[idx] != nullptr) + return it(key); + return end(); + } + + const_iterator find(const key_type& key) const + { + key_type idx = Map::Idx(key); + if (static_cast(idx) < self()->Keys(key).size() && self()->Keys(key)[idx] != nullptr) + return it(key); + return end(); + } +}; + +template +class SparseFlatMap : public SparseFlatMapCore, T, V> +{ +public: + SparseFlatMap() = default; + void copy(const SparseFlatMap&) {}; + void swap(SparseFlatMap&) {}; + void clearKeys() {}; +}; + + +/** + * DualFlatMap is a wrapper around SparseFlatMap when keys can start at two vastly different values. + * This avoid having a very large, empty key array, but instead two more compact key arrays. + */ +template +class DualFlatMap : public SparseFlatMapCore, T, V> +{ +protected: + using og = SparseFlatMapCore, T, V>; + friend og; + + static typename og::key_type Idx(const typename og::key_type key) + { + return key < SECONDARY_ID_START ? key : key - SECONDARY_ID_START; + } + + typename og::keys_container& Keys(const typename og::key_type key) + { + return key < SECONDARY_ID_START ? og::m_Keys : m_SecondaryKeys; + } + + const typename og::keys_container& Keys(const typename og::key_type key) const + { + return key < SECONDARY_ID_START ? og::m_Keys : m_SecondaryKeys; + } + +private: + typename og::keys_container m_SecondaryKeys; + +public: + + DualFlatMap() + { + m_SecondaryKeys.reserve(4096); + } + + void copy(const DualFlatMap& o) + { + m_SecondaryKeys = o.m_SecondaryKeys; + } + + void swap(DualFlatMap& o) + { + m_SecondaryKeys.swap(o.m_SecondaryKeys); + } + + void clearKeys() + { + m_SecondaryKeys.clear(); + } +}; + +template +struct SerializeSparseFlatMap +{ + template + void operator()(ISerializer& serialize, const char* UNUSED(name), flatMap& value) + { + static_assert(std::is_convertible::value, "key must be convertible to a u32"); + size_t len = value.size(); + serialize.NumberU32_Unbounded("length", (u32)len); + size_t count = 0; + for (auto& data : value) + { + serialize.NumberU32_Unbounded("key", data.first); + VSerializer()(serialize, "value", data.second); + count++; + } + // test to see if the sparse flat map count wasn't wrong + // (which causes a crashing deserialisation) + ENSURE(count == len); + } + + template + void operator()(IDeserializer& deserialize, const char* UNUSED(name), flatMap& value) + { + static_assert(std::is_convertible::value, "key must be convertible to a u32"); + value.clear(); + uint32_t len; + deserialize.NumberU32_Unbounded("length", len); + for (size_t i = 0; i < len; ++i) + { + typename flatMap::key_type k; + typename flatMap::mapped_type v; + deserialize.NumberU32_Unbounded("key", k); + VSerializer()(deserialize, "value", v); + value.insert_or_assign(k, v); + } + } +}; + +#endif Index: source/simulation2/system/ComponentManager.h =================================================================== --- source/simulation2/system/ComponentManager.h +++ source/simulation2/system/ComponentManager.h @@ -23,6 +23,7 @@ #include "scriptinterface/ScriptInterface.h" #include "scriptinterface/ScriptVal.h" #include "simulation2/helpers/Player.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "ps/Filesystem.h" #include @@ -272,7 +273,7 @@ typedef std::pair InterfacePair; typedef std::vector InterfaceList; - typedef boost::unordered_map InterfaceListUnordered; + typedef DualFlatMap InterfaceListUnordered; InterfaceList GetEntitiesWithInterface(InterfaceId iid) const; const InterfaceListUnordered& GetEntitiesWithInterfaceUnordered(InterfaceId iid) const; @@ -352,11 +353,23 @@ // TODO: some of these should be vectors std::map m_ComponentTypesById; - std::vector m_ScriptedSystemComponents; - std::vector > m_ComponentsByInterface; // indexed by InterfaceId - std::map > m_ComponentsByTypeId; - std::map > m_LocalMessageSubscriptions; - std::map > m_GlobalMessageSubscriptions; + std::vector m_ScriptedSystemComponents; + + // Use a DualFlatMap for fast iteration and fast random access, but also local entity support. + using EntCompMap = DualFlatMap; + // To be extremely fast, use a vector to index items. + using ComponentMap = std::vector; + ComponentMap m_ComponentsByInterface; // indexed by InterfaceId + ComponentMap m_ComponentsByTypeId; // indexed by ComponentTypeId + + // Since MessageMap keeps a pointer to vector data, we must be careful to update them when resizing. + void ResizeComponentsByTypeId(size_t new_size); + + // Map directly a pointer to the correct ComponentMap to skip several dereferences. + using MessageMap = SparseFlatMap >; + MessageMap m_LocalMessageSubscriptions; + MessageMap m_GlobalMessageSubscriptions; + std::map m_ComponentTypeIdsByName; std::map m_MessageTypeIdsByName; std::map m_MessageTypeNamesById; Index: source/simulation2/system/ComponentManager.cpp =================================================================== --- source/simulation2/system/ComponentManager.cpp +++ source/simulation2/system/ComponentManager.cpp @@ -178,6 +178,7 @@ // Allocate a new cid number cid = componentManager->m_NextScriptComponentTypeId++; componentManager->m_ComponentTypeIdsByName[cname] = cid; + componentManager->ResizeComponentsByTypeId(cid + 1); if (systemComponent) componentManager->MarkScriptedComponentForSystemEntity(cid); } @@ -213,18 +214,19 @@ } // Remove the old component type's message subscriptions - std::map >::iterator it; - for (it = componentManager->m_LocalMessageSubscriptions.begin(); it != componentManager->m_LocalMessageSubscriptions.end(); ++it) + for (std::pair >& subscribers : componentManager->m_LocalMessageSubscriptions) { - std::vector& types = it->second; - std::vector::iterator ctit = find(types.begin(), types.end(), cid); + std::vector& types = subscribers.second; + EntCompMap* start = componentManager->m_ComponentsByTypeId.data(); + std::vector::iterator ctit = std::find_if(types.begin(), types.end(), [=](EntCompMap* ptr) { return (ptr - start) == cid; }); if (ctit != types.end()) types.erase(ctit); } - for (it = componentManager->m_GlobalMessageSubscriptions.begin(); it != componentManager->m_GlobalMessageSubscriptions.end(); ++it) + for (std::pair >& subscribers : componentManager->m_GlobalMessageSubscriptions) { - std::vector& types = it->second; - std::vector::iterator ctit = find(types.begin(), types.end(), cid); + std::vector& types = subscribers.second; + EntCompMap* start = componentManager->m_ComponentsByTypeId.data(); + std::vector::iterator ctit = std::find_if(types.begin(), types.end(), [=](EntCompMap* ptr) { return (ptr - start) == cid; }); if (ctit != types.end()) types.erase(ctit); } @@ -298,19 +300,15 @@ componentManager->m_CurrentComponent = CID__Invalid; + // For every script component with this cid, we need to switch its + // prototype from the old constructor's prototype property to the new one's if (mustReloadComponents) - { - // For every script component with this cid, we need to switch its - // prototype from the old constructor's prototype property to the new one's - const std::map& comps = componentManager->m_ComponentsByTypeId[cid]; - std::map::const_iterator eit = comps.begin(); - for (; eit != comps.end(); ++eit) + for (const std::pair& entComp : componentManager->m_ComponentsByTypeId[cid]) { - JS::RootedValue instance(cx, eit->second->GetJSInstance()); + JS::RootedValue instance(cx, entComp.second->GetJSInstance()); if (!instance.isNull()) componentManager->m_ScriptInterface.SetPrototype(instance, protoVal); } - } } void CComponentManager::Script_RegisterComponentType(ScriptInterface::CxPrivate* pCxPrivate, int iid, const std::string& cname, JS::HandleValue ctor) @@ -391,10 +389,9 @@ CComponentManager* componentManager = static_cast (pCxPrivate->pCBData); std::vector ret; - const InterfaceListUnordered& ents = componentManager->GetEntitiesWithInterfaceUnordered(iid); - for (InterfaceListUnordered::const_iterator it = ents.begin(); it != ents.end(); ++it) - if (!ENTITY_IS_LOCAL(it->first)) - ret.push_back(it->first); + for (const std::pair& entComp : componentManager->GetEntitiesWithInterfaceUnordered(iid)) + if (!ENTITY_IS_LOCAL(entComp.first)) + ret.push_back(entComp.first); std::sort(ret.begin(), ret.end()); return ret; } @@ -495,20 +492,17 @@ m_DynamicMessageSubscriptionsNonsyncByComponent.clear(); // Delete all IComponents - std::map >::iterator iit = m_ComponentsByTypeId.begin(); - for (; iit != m_ComponentsByTypeId.end(); ++iit) + for (size_t cid = 0; cid < m_ComponentsByTypeId.size(); ++cid) { - std::map::iterator eit = iit->second.begin(); - for (; eit != iit->second.end(); ++eit) + for (std::pair& entComp : m_ComponentsByTypeId[cid]) { - eit->second->Deinit(); - m_ComponentTypesById[iit->first].dealloc(eit->second); + entComp.second->Deinit(); + m_ComponentTypesById[cid].dealloc(entComp.second); } } - std::vector >::iterator ifcit = m_ComponentsByInterface.begin(); - for (; ifcit != m_ComponentsByInterface.end(); ++ifcit) - ifcit->clear(); + for (size_t iid = 0; iid < m_ComponentsByInterface.size(); ++iid) + m_ComponentsByInterface[iid].clear(); m_ComponentsByTypeId.clear(); @@ -534,17 +528,19 @@ void CComponentManager::RegisterComponentType(InterfaceId iid, ComponentTypeId cid, AllocFunc alloc, DeallocFunc dealloc, const char* name, const std::string& schema) { + m_ComponentTypeIdsByName[name] = cid; + ResizeComponentsByTypeId(cid + 1); ComponentType c(CT_Native, iid, alloc, dealloc, name, schema, DefPersistentRooted()); m_ComponentTypesById.insert(std::make_pair(cid, std::move(c))); - m_ComponentTypeIdsByName[name] = cid; } void CComponentManager::RegisterComponentTypeScriptWrapper(InterfaceId iid, ComponentTypeId cid, AllocFunc alloc, DeallocFunc dealloc, const char* name, const std::string& schema) { + m_ComponentTypeIdsByName[name] = cid; + ResizeComponentsByTypeId(cid + 1); ComponentType c(CT_ScriptWrapper, iid, alloc, dealloc, name, schema, DefPersistentRooted()); m_ComponentTypesById.insert(std::make_pair(cid, std::move(c))); - m_ComponentTypeIdsByName[name] = cid; // TODO: merge with RegisterComponentType } @@ -563,18 +559,50 @@ { // TODO: verify mtid ENSURE(m_CurrentComponent != CID__Invalid); - std::vector& types = m_LocalMessageSubscriptions[mtid]; - types.push_back(m_CurrentComponent); - std::sort(types.begin(), types.end()); // TODO: just sort once at the end of LoadComponents + ENSURE(static_cast(m_ComponentsByTypeId.size()) > m_CurrentComponent); + m_LocalMessageSubscriptions[mtid].push_back(&m_ComponentsByTypeId[m_CurrentComponent]); } void CComponentManager::SubscribeGloballyToMessageType(MessageTypeId mtid) { // TODO: verify mtid ENSURE(m_CurrentComponent != CID__Invalid); - std::vector& types = m_GlobalMessageSubscriptions[mtid]; - types.push_back(m_CurrentComponent); - std::sort(types.begin(), types.end()); // TODO: just sort once at the end of LoadComponents + ENSURE(static_cast(m_ComponentsByTypeId.size()) > m_CurrentComponent); + m_GlobalMessageSubscriptions[mtid].push_back(&m_ComponentsByTypeId[m_CurrentComponent]); +} + +void CComponentManager::ResizeComponentsByTypeId(size_t new_size) +{ + if (m_ComponentsByTypeId.size() >= new_size) + return; + + if (m_ComponentsByTypeId.capacity() >= new_size) + { + m_ComponentsByTypeId.resize(new_size); + return; + } + // Message subscriptions keep raw pointers, so when invalidated we must update them. + // Convert these pointers back to component types IDs through safe pointer arithmetic, + // resize, then re-update subscriptions. + // This is somewhat inefficient but that should never be a problem since it happens at initialisation. + std::unordered_map > local, global; + for (const std::pair>& subscribers : m_LocalMessageSubscriptions) + for (EntCompMap* map : subscribers.second) + local[subscribers.first].push_back(map - m_ComponentsByTypeId.data()); + for (const std::pair>& subscribers : m_GlobalMessageSubscriptions) + for (EntCompMap* map : subscribers.second) + global[subscribers.first].push_back(map - m_ComponentsByTypeId.data()); + + m_LocalMessageSubscriptions.clear(); + m_GlobalMessageSubscriptions.clear(); + m_ComponentsByTypeId.resize(new_size); + + for (const std::pair >& new_map : local) + for (ComponentTypeId cid : new_map.second) + m_LocalMessageSubscriptions[new_map.first].push_back(&m_ComponentsByTypeId.at(cid)); + for (const std::pair >& new_map : global) + for (ComponentTypeId cid : new_map.second) + m_GlobalMessageSubscriptions[new_map.first].push_back(&m_ComponentsByTypeId.at(cid)); } void CComponentManager::FlattenDynamicSubscriptions() @@ -741,14 +769,15 @@ ENSURE((size_t)ct.iid < m_ComponentsByInterface.size()); - boost::unordered_map& emap1 = m_ComponentsByInterface[ct.iid]; + EntCompMap& emap1 = m_ComponentsByInterface[ct.iid]; if (emap1.find(ent.GetId()) != emap1.end()) { LOGERROR("Multiple components for interface %d", ct.iid); return NULL; } - std::map& emap2 = m_ComponentsByTypeId[cid]; + ResizeComponentsByTypeId(cid + 1); + EntCompMap& emap2 = m_ComponentsByTypeId[cid]; // If this is a scripted component, construct the appropriate JS object first JS::RootedValue obj(cx); @@ -770,8 +799,9 @@ component->SetSimContext(m_SimContext); // Store a reference to the new component - emap1.insert(std::make_pair(ent.GetId(), component)); - emap2.insert(std::make_pair(ent.GetId(), component)); + emap1.insert_or_assign(ent.GetId(), component); + emap2.insert_or_assign(ent.GetId(), component); + // TODO: We need to more careful about this - if an entity is constructed by a component // while we're iterating over all components, this will invalidate the iterators and everything // will break. @@ -790,10 +820,10 @@ // Just add it into the by-interface map, not the by-component-type map, // so it won't be considered for messages or deletion etc - boost::unordered_map& emap1 = m_ComponentsByInterface.at(iid); + EntCompMap& emap1 = m_ComponentsByInterface.at(iid); if (emap1.find(ent.GetId()) != emap1.end()) debug_warn(L"Multiple components for interface"); - emap1.insert(std::make_pair(ent.GetId(), &component)); + emap1.insert_or_assign(ent.GetId(), &component); SEntityComponentCache* cache = ent.GetComponentCache(); ENSURE(cache != NULL && iid < (int)cache->numInterfaces && cache->interfaces[iid] == NULL); @@ -923,29 +953,24 @@ FlattenDynamicSubscriptions(); // Destroy the components, and remove from m_ComponentsByTypeId: - std::map >::iterator iit = m_ComponentsByTypeId.begin(); - for (; iit != m_ComponentsByTypeId.end(); ++iit) + for (size_t cid = 1; cid < m_ComponentsByTypeId.size(); ++cid) { - std::map::iterator eit = iit->second.find(ent); - if (eit != iit->second.end()) + EntCompMap::iterator eit = m_ComponentsByTypeId[cid].find(ent); + if (eit != m_ComponentsByTypeId[cid].end()) { eit->second->Deinit(); RemoveComponentDynamicSubscriptions(eit->second); - m_ComponentTypesById[iit->first].dealloc(eit->second); - iit->second.erase(ent); - handle.GetComponentCache()->interfaces[m_ComponentTypesById[iit->first].iid] = NULL; + m_ComponentTypesById[cid].dealloc(eit->second); + m_ComponentsByTypeId[cid].erase(ent); + handle.GetComponentCache()->interfaces[m_ComponentTypesById[cid].iid] = NULL; } } free(handle.GetComponentCache()); m_ComponentCaches.erase(ent); - // Remove from m_ComponentsByInterface - std::vector >::iterator ifcit = m_ComponentsByInterface.begin(); - for (; ifcit != m_ComponentsByInterface.end(); ++ifcit) - { - ifcit->erase(ent); - } + for (size_t iid = 1; iid < m_ComponentsByInterface.size(); ++iid) + m_ComponentsByInterface[iid].erase(ent); } } } @@ -958,7 +983,7 @@ return NULL; } - boost::unordered_map::const_iterator eit = m_ComponentsByInterface[iid].find(ent); + EntCompMap::const_iterator eit = m_ComponentsByInterface[iid].find(ent); if (eit == m_ComponentsByInterface[iid].end()) { // This entity doesn't implement this interface @@ -980,9 +1005,8 @@ ret.reserve(m_ComponentsByInterface[iid].size()); - boost::unordered_map::const_iterator it = m_ComponentsByInterface[iid].begin(); - for (; it != m_ComponentsByInterface[iid].end(); ++it) - ret.push_back(*it); + for (const std::pair& entComp : m_ComponentsByInterface[iid]) + ret.push_back(entComp); std::sort(ret.begin(), ret.end()); // lexicographic pair comparison means this'll sort by entity ID @@ -1005,25 +1029,16 @@ { PROFILE2_IFSPIKE("Post Message", 0.0005); PROFILE2_ATTR("%s", msg.GetScriptHandlerName()); + // Send the message to components of ent, that subscribed locally to this message - std::map >::const_iterator it; - it = m_LocalMessageSubscriptions.find(msg.GetType()); + MessageMap::const_iterator it = m_LocalMessageSubscriptions.find(msg.GetType()); if (it != m_LocalMessageSubscriptions.end()) - { - std::vector::const_iterator ctit = it->second.begin(); - for (; ctit != it->second.end(); ++ctit) + for (EntCompMap* entCompMap : it->second) { - // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); - if (emap == m_ComponentsByTypeId.end()) - continue; - - // Send the message to all of them - std::map::const_iterator eit = emap->second.find(ent); - if (eit != emap->second.end()) + EntCompMap::iterator eit = entCompMap->find(ent); + if (eit != entCompMap->end()) eit->second->HandleMessage(msg, false); } - } SendGlobalMessage(ent, msg); } @@ -1031,24 +1046,11 @@ void CComponentManager::BroadcastMessage(const CMessage& msg) { // Send the message to components of all entities that subscribed locally to this message - std::map >::const_iterator it; - it = m_LocalMessageSubscriptions.find(msg.GetType()); + MessageMap::const_iterator it = m_LocalMessageSubscriptions.find(msg.GetType()); if (it != m_LocalMessageSubscriptions.end()) - { - std::vector::const_iterator ctit = it->second.begin(); - for (; ctit != it->second.end(); ++ctit) - { - // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); - if (emap == m_ComponentsByTypeId.end()) - continue; - - // Send the message to all of them - std::map::const_iterator eit = emap->second.begin(); - for (; eit != emap->second.end(); ++eit) - eit->second->HandleMessage(msg, false); - } - } + for (EntCompMap* entCompMap : it->second) + for (std::pair& entComp : *entCompMap) + entComp.second->HandleMessage(msg, false); SendGlobalMessage(INVALID_ENTITY, msg); } @@ -1060,34 +1062,23 @@ // (Common functionality for PostMessage and BroadcastMessage) // Send the message to components of all entities that subscribed globally to this message - std::map >::const_iterator it; - it = m_GlobalMessageSubscriptions.find(msg.GetType()); + MessageMap::const_iterator it = m_GlobalMessageSubscriptions.find(msg.GetType()); if (it != m_GlobalMessageSubscriptions.end()) - { - std::vector::const_iterator ctit = it->second.begin(); - for (; ctit != it->second.end(); ++ctit) + for (EntCompMap* entCompMap : it->second) { // Special case: Messages for local entities shouldn't be sent to script // components that subscribed globally, so that we don't have to worry about // them accidentally picking up non-network-synchronised data. if (ENTITY_IS_LOCAL(ent)) { - std::map::const_iterator it = m_ComponentTypesById.find(*ctit); + ComponentTypeId cid = entCompMap - m_ComponentsByTypeId.data(); + std::map::const_iterator it = m_ComponentTypesById.find(cid); if (it != m_ComponentTypesById.end() && it->second.type == CT_Script) continue; } - - // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); - if (emap == m_ComponentsByTypeId.end()) - continue; - - // Send the message to all of them - std::map::const_iterator eit = emap->second.begin(); - for (; eit != emap->second.end(); ++eit) - eit->second->HandleMessage(msg, true); + for (std::pair& entComp : *entCompMap) + entComp.second->HandleMessage(msg, true); } - } // Send the message to component instances that dynamically subscribed to this message std::map::iterator dit = m_DynamicMessageSubscriptionsNonsync.find(msg.GetType()); Index: source/simulation2/system/ComponentManagerSerialization.cpp =================================================================== --- source/simulation2/system/ComponentManagerSerialization.cpp +++ source/simulation2/system/ComponentManagerSerialization.cpp @@ -55,37 +55,27 @@ serializer.TextLine("entities:"); // We want the output to be grouped by entity ID, so invert the CComponentManager data structures - std::map > components; - //std::map names; + DualFlatMap, FIRST_LOCAL_ENTITY> components; + for (size_t cid = 1; cid < m_ComponentsByTypeId.size(); ++cid) + for (const std::pair& entComp : m_ComponentsByTypeId[cid]) + components[entComp.first][cid] = entComp.second; - std::map >::const_iterator ctit = m_ComponentsByTypeId.begin(); - for (; ctit != m_ComponentsByTypeId.end(); ++ctit) - { - std::map::const_iterator eit = ctit->second.begin(); - for (; eit != ctit->second.end(); ++eit) - { - components[eit->first][ctit->first] = eit->second; - } - } - - std::map >::const_iterator cit = components.begin(); - for (; cit != components.end(); ++cit) + for (const std::pair >& ents : components) { std::stringstream n; - n << "- id: " << cit->first; + n << "- id: " << ents.first; serializer.TextLine(n.str()); - if (ENTITY_IS_LOCAL(cit->first)) + if (ENTITY_IS_LOCAL(ents.first)) serializer.TextLine(" type: local"); - std::map::const_iterator ctit = cit->second.begin(); - for (; ctit != cit->second.end(); ++ctit) + for (const std::pair& comp : ents.second) { std::stringstream n; - n << " " << LookupComponentTypeName(ctit->first) << ":"; + n << " " << LookupComponentTypeName(comp.first) << ":"; serializer.TextLine(n.str()); serializer.Indent(4); - ctit->second->Serialize(serializer); + comp.second->Serialize(serializer); serializer.Dedent(4); } serializer.TextLine(""); @@ -109,19 +99,18 @@ serializer.StringASCII("rng", SerializeRNG(m_RNG), 0, 32); serializer.NumberU32_Unbounded("next entity id", m_NextEntityId); - std::map >::const_iterator cit = m_ComponentsByTypeId.begin(); - for (; cit != m_ComponentsByTypeId.end(); ++cit) + for (size_t cid = 1; cid < m_ComponentsByTypeId.size(); ++cid) { // In quick mode, only check unit positions - if (quick && !(cit->first == CID_Position)) + if (quick && !(cid == CID_Position)) continue; // Only emit component types if they have a component that will be serialized bool needsSerialization = false; - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& entComp : m_ComponentsByTypeId[cid]) { // Don't serialize local entities - if (ENTITY_IS_LOCAL(eit->first)) + if (ENTITY_IS_LOCAL(entComp.first)) continue; needsSerialization = true; @@ -131,16 +120,16 @@ if (!needsSerialization) continue; - serializer.NumberI32_Unbounded("component type id", cit->first); + serializer.NumberI32_Unbounded("component type id", cid); - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& entComp : m_ComponentsByTypeId[cid]) { // Don't serialize local entities - if (ENTITY_IS_LOCAL(eit->first)) + if (ENTITY_IS_LOCAL(entComp.first)) continue; - serializer.NumberU32_Unbounded("entity id", eit->first); - eit->second->Serialize(serializer); + serializer.NumberU32_Unbounded("entity id", entComp.first); + entComp.second->Serialize(serializer); } } @@ -188,21 +177,19 @@ serializer.StringASCII("rng", SerializeRNG(m_RNG), 0, 32); serializer.NumberU32_Unbounded("next entity id", m_NextEntityId); - std::map >::const_iterator cit; - uint32_t numSystemComponentTypes = 0; uint32_t numComponentTypes = 0; std::set serializedSystemComponentTypes; std::set serializedComponentTypes; - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (size_t cid = 1; cid < m_ComponentsByTypeId.size(); ++cid) { // Only emit component types if they have a component that will be serialized bool needsSerialization = false; - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& entComp : m_ComponentsByTypeId[cid]) { // Don't serialize local entities, and handle SYSTEM_ENTITY separately - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(entComp.first) || entComp.first == SYSTEM_ENTITY) continue; needsSerialization = true; @@ -212,24 +199,24 @@ if (needsSerialization) { numComponentTypes++; - serializedComponentTypes.insert(cit->first); + serializedComponentTypes.insert(cid); } - if (cit->second.find(SYSTEM_ENTITY) != cit->second.end()) + if (m_ComponentsByTypeId[cid].find(SYSTEM_ENTITY) != m_ComponentsByTypeId[cid].end()) { numSystemComponentTypes++; - serializedSystemComponentTypes.insert(cit->first); + serializedSystemComponentTypes.insert(cid); } } serializer.NumberU32_Unbounded("num system component types", numSystemComponentTypes); - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (size_t cid = 1; cid < m_ComponentsByTypeId.size(); ++cid) { - if (serializedSystemComponentTypes.find(cit->first) == serializedSystemComponentTypes.end()) + if (serializedSystemComponentTypes.find(cid) == serializedSystemComponentTypes.end()) continue; - std::map::const_iterator ctit = m_ComponentTypesById.find(cit->first); + std::map::const_iterator ctit = m_ComponentTypesById.find(cid); if (ctit == m_ComponentTypesById.end()) { debug_warn(L"Invalid ctit"); // this should never happen @@ -238,8 +225,8 @@ serializer.StringASCII("name", ctit->second.name, 0, 255); - std::map::const_iterator eit = cit->second.find(SYSTEM_ENTITY); - if (eit == cit->second.end()) + EntCompMap::const_iterator eit = m_ComponentsByTypeId[cid].find(SYSTEM_ENTITY); + if (eit == m_ComponentsByTypeId[cid].end()) { debug_warn(L"Invalid eit"); // this should never happen return false; @@ -249,12 +236,12 @@ serializer.NumberU32_Unbounded("num component types", numComponentTypes); - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (size_t cid = 1; cid < m_ComponentsByTypeId.size(); ++cid) { - if (serializedComponentTypes.find(cit->first) == serializedComponentTypes.end()) + if (serializedComponentTypes.find(cid) == serializedComponentTypes.end()) continue; - std::map::const_iterator ctit = m_ComponentTypesById.find(cit->first); + std::map::const_iterator ctit = m_ComponentTypesById.find(cid); if (ctit == m_ComponentTypesById.end()) { debug_warn(L"Invalid ctit"); // this should never happen @@ -265,10 +252,10 @@ // Count the components before serializing any of them uint32_t numComponents = 0; - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& entComp : m_ComponentsByTypeId[cid]) { // Don't serialize local entities or SYSTEM_ENTITY - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(entComp.first) || entComp.first == SYSTEM_ENTITY) continue; numComponents++; @@ -278,14 +265,14 @@ serializer.NumberU32_Unbounded("num components", numComponents); // Serialize the components now - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& entComp : m_ComponentsByTypeId[cid]) { // Don't serialize local entities or SYSTEM_ENTITY - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(entComp.first) || entComp.first == SYSTEM_ENTITY) continue; - serializer.NumberU32_Unbounded("entity id", eit->first); - eit->second->Serialize(serializer); + serializer.NumberU32_Unbounded("entity id", entComp.first); + entComp.second->Serialize(serializer); } } Index: source/simulation2/system/EntityMap.h =================================================================== --- source/simulation2/system/EntityMap.h +++ /dev/null @@ -1,282 +0,0 @@ -/* Copyright (C) 2013 Wildfire Games. - * This file is part of 0 A.D. - * - * 0 A.D. is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 2 of the License, or - * (at your option) any later version. - * - * 0 A.D. is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with 0 A.D. If not, see . - */ -#ifndef INCLUDED_ENTITYMAP -#define INCLUDED_ENTITYMAP - -#include "Entity.h" - -/** - * A fast replacement for map. - * We make the following assumptions: - * - entity id's (keys) are unique - * - modifications (add / delete) are far less frequent then look-ups - * - preformance for iteration is important - */ -template class EntityMap -{ -private: - EntityMap(const EntityMap&); // non-copyable - EntityMap& operator=(const EntityMap&); // non-copyable - -public: - typedef entity_id_t key_type; - typedef T mapped_type; - template struct key_val { - typedef K first_type; - typedef V second_type; - K first; - V second; - }; - typedef key_val value_type; - -private: - size_t m_BufferSize; // number of elements in the buffer - size_t m_BufferCapacity; // capacity of the buffer - value_type* m_Buffer; // vector with all the mapped key-value pairs - - size_t m_Count; // number of 'valid' entity id's - -public: - - inline EntityMap() : m_BufferSize(1), m_BufferCapacity(4096), m_Count(0) - { - // for entitymap we allocate the buffer right away - // with first element in buffer being the Invalid Entity - m_Buffer = (value_type*)malloc(sizeof(value_type) * (m_BufferCapacity + 1)); - - // create the first element: - m_Buffer[0].first = INVALID_ENTITY; - m_Buffer[1].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF - } - inline ~EntityMap() - { - free(m_Buffer); - } - - // Iterators - template struct _iter : public std::iterator - { - U* val; - inline _iter(U* init) : val(init) {} - inline U& operator*() { return *val; } - inline U* operator->() { return val; } - inline _iter& operator++() // ++it - { - ++val; - while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities - return *this; - } - inline _iter& operator++(int) // it++ - { - U* ptr = val; - ++val; - while (val->first == INVALID_ENTITY) ++val; // skip any invalid entities - return ptr; - } - inline bool operator==(_iter other) { return val == other.val; } - inline bool operator!=(_iter other) { return val != other.val; } - inline operator _iter() const { return _iter(val); } - }; - - typedef _iter iterator; - typedef _iter const_iterator; - - inline iterator begin() - { - value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY - while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities - return ptr; - } - inline iterator end() - { - return iterator(m_Buffer + m_BufferSize); - } - inline const_iterator begin() const - { - value_type* ptr = m_Buffer + 1; // skip the first INVALID_ENTITY - while (ptr->first == INVALID_ENTITY) ++ptr; // skip any other invalid entities - return ptr; - } - inline const_iterator end() const - { - return const_iterator(m_Buffer + m_BufferSize); - } - - // Size - inline bool empty() const { return m_Count == 0; } - inline size_t size() const { return m_Count; } - - // Modification - void insert(const key_type key, const mapped_type& value) - { - if (key >= m_BufferCapacity) // do we need to resize buffer? - { - size_t newCapacity = m_BufferCapacity + 4096; - while (key >= newCapacity) newCapacity += 4096; - // always allocate +1 behind the scenes, because end() must have a 0xFFFFFFFF key - value_type* mem = (value_type*)realloc(m_Buffer, sizeof(value_type) * (newCapacity + 1)); - if (!mem) - { - debug_warn("EntityMap::insert() realloc failed! Out of memory."); - throw std::bad_alloc(); // fail to expand and insert - } - m_BufferCapacity = newCapacity; - m_Buffer = mem; - goto fill_gaps; - } - else if (key > m_BufferSize) // weird insert far beyond the end - { -fill_gaps: - // set all entity id's to INVALID_ENTITY inside the new range - for (size_t i = m_BufferSize; i <= key; ++i) - m_Buffer[i].first = INVALID_ENTITY; - m_BufferSize = key; // extend the new size - } - - value_type& item = m_Buffer[key]; - key_type oldKey = item.first; - item.first = key; - if (key == m_BufferSize) // push_back - { - ++m_BufferSize; // expand - ++m_Count; - new (&item.second) mapped_type(value); // copy ctor to init - m_Buffer[m_BufferSize].first = 0xFFFFFFFF; // ensure end() always has 0xFFFFFFFF - } - else if(!item.first) // insert new to middle - { - ++m_Count; - new (&item.second) mapped_type(value); // copy ctor to init - } - else // set existing value - { - if (oldKey == INVALID_ENTITY) - m_Count++; - item.second = value; // overwrite existing - } - } - - void erase(iterator it) - { - value_type* ptr = it.val; - if (ptr->first != INVALID_ENTITY) - { - ptr->first = INVALID_ENTITY; - ptr->second.~T(); // call dtor - --m_Count; - } - } - void erase(const entity_id_t key) - { - if (key < m_BufferSize) - { - value_type* ptr = m_Buffer + key; - if (ptr->first != INVALID_ENTITY) - { - ptr->first = INVALID_ENTITY; - ptr->second.~T(); // call dtor - --m_Count; - } - } - } - inline void clear() - { - // orphan whole range - value_type* ptr = m_Buffer; - value_type* end = m_Buffer + m_BufferSize; - for (; ptr != end; ++ptr) - { - if (ptr->first != INVALID_ENTITY) - { - ptr->first = INVALID_ENTITY; - ptr->second.~T(); // call dtor - } - } - m_Count = 0; // no more valid entities - } - - // Operations - inline iterator find(const entity_id_t key) - { - if (key < m_BufferSize) // is this key in the range of existing entitites? - { - value_type* ptr = m_Buffer + key; - if (ptr->first != INVALID_ENTITY) - return ptr; - } - return m_Buffer + m_BufferSize; // return iterator end() - } - inline const_iterator find(const entity_id_t key) const - { - if (key < m_BufferSize) // is this key in the range of existing entitites? - { - const value_type* ptr = m_Buffer + key; - if (ptr->first != INVALID_ENTITY) - return ptr; - } - return m_Buffer + m_BufferSize; // return iterator end() - } - inline size_t count(const entity_id_t key) const - { - if (key < m_BufferSize) - { - if (m_Buffer[key].first != INVALID_ENTITY) - return 1; - } - return 0; - } -}; - -template -struct SerializeEntityMap -{ - template - void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap& value) - { - size_t len = value.size(); - serialize.NumberU32_Unbounded("length", (u32)len); - size_t count = 0; - for (typename EntityMap::iterator it = value.begin(); it != value.end(); ++it) - { - serialize.NumberU32_Unbounded("key", it->first); - VSerializer()(serialize, "value", it->second); - count++; - } - // test to see if the entityMap count wasn't wrong - // (which causes a crashing deserialisation) - ENSURE(count == len); - } - - template - void operator()(IDeserializer& deserialize, const char* UNUSED(name), EntityMap& value) - { - value.clear(); - uint32_t len; - deserialize.NumberU32_Unbounded("length", len); - for (size_t i = 0; i < len; ++i) - { - entity_id_t k; - V v; - deserialize.NumberU32_Unbounded("key", k); - VSerializer()(deserialize, "value", v); - value.insert(k, v); - } - } -}; - - -#endif Index: source/simulation2/tests/test_ComponentManager.h =================================================================== --- source/simulation2/tests/test_ComponentManager.h +++ source/simulation2/tests/test_ComponentManager.h @@ -199,6 +199,7 @@ TS_ASSERT_EQUALS(static_cast (man.QueryInterface(ent4, IID_Test1))->GetX(), 11000); TS_ASSERT_EQUALS(static_cast (man.QueryInterface(ent4, IID_Test2))->GetX(), 21000); + printf("Start of test message"); // Test_1A subscribed locally to msg1, nothing subscribed globally man.PostMessage(ent1, msg1); man.PostMessage(ent1, msg2); Index: source/simulation2/tests/test_EntityMap.h =================================================================== --- source/simulation2/tests/test_EntityMap.h +++ /dev/null @@ -1,308 +0,0 @@ -/* Copyright (C) 2019 Wildfire Games. - * This file is part of 0 A.D. - * - * 0 A.D. is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 2 of the License, or - * (at your option) any later version. - * - * 0 A.D. is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with 0 A.D. If not, see . - */ - -#include "lib/self_test.h" -#include "lib/timer.h" - -#include "simulation2/serialization/ISerializer.h" -#include "simulation2/serialization/IDeserializer.h" - -#include "simulation2/system/EntityMap.h" - -class TestEntityMap : public CxxTest::TestSuite -{ -public: - void setUp() - { - } - - void tearDown() - { - } - - void test_insert() - { - EntityMap test; - - TS_ASSERT(test.empty()); - - test.insert(1,1); - test.insert(2,2); - test.insert(3,3); - test.insert(4,4); - test.insert(4,5); - test.insert(4,6); - -// TS_ASSERT(test.m_Data.size() == 5); -// TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY); - TS_ASSERT(test.size() == 4); - TS_ASSERT(test.find(3)->second == 3); - TS_ASSERT(test.find(4)->second == 6); - - test.insert(10,7); -// TS_ASSERT(test.m_Data.size() == 11); -// TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY); - TS_ASSERT(test.size() == 5); - TS_ASSERT(test.find(4)->second == 6); - TS_ASSERT(test.find(5) == test.end()); - TS_ASSERT(test.find(6) == test.end()); - TS_ASSERT(test.find(7) == test.end()); - TS_ASSERT(test.find(8) == test.end()); - TS_ASSERT(test.find(9) == test.end()); - TS_ASSERT(test.find(10)->second == 7); - -// EntityMap test2; - -// test2.insert(8,5); -// TS_ASSERT(test2.find(8)->second == 5); -// TS_ASSERT(test2.m_Data.size() == 5); -// TS_ASSERT(test2.size() == 1); - - } - void test_iterators() - { - EntityMap test; - - test.insert(1,1); - test.insert(2,2); - test.insert(3,3); - test.insert(4,4); - - EntityMap::iterator it = test.begin(); - TS_ASSERT(it->first == 1); - ++it; - TS_ASSERT(it->first == 2); - ++it; // it++ incorrectly returns a pointer in svn - TS_ASSERT(it->first == 3); - it = test.end(); -// TS_ASSERT(it->first == test.m_Data.back().first); - - EntityMap::const_iterator cit = test.begin(); - TS_ASSERT(cit->first == 1); - cit = test.end(); -// TS_ASSERT(cit->first == test.m_Data.back().first); - - size_t iter = 0; - for (EntityMap::value_type& v : test) - { - ++iter; - TS_ASSERT(test.find(iter)->second == (int)iter); - TS_ASSERT(test.find(iter)->second == v.second); - } - TS_ASSERT(iter == 4); - - test.clear(); - - test.insert(10,1); - test.insert(20,2); - test.insert(30,3); - test.insert(40,4); - - it = test.begin(); - TS_ASSERT(it->second == 1); - ++it; // it++ incorrectly returns a pointer in svn - TS_ASSERT(it->second == 2); - ++it; - TS_ASSERT(it->second == 3); - it = test.end(); -// TS_ASSERT(it->first == test.m_Data.back().first); - - } - - void test_erase() - { - EntityMap test; - test.insert(1,1); - test.insert(2,2); - test.insert(3,3); - test.insert(4,4); - - test.erase(2); - -// TS_ASSERT(test.m_Data.size() == 5); - TS_ASSERT(test.size() == 3); - TS_ASSERT(test.find(2) == test.end()); - - test.erase(1); - test.erase(3); - test.erase(4);// TS_ASSERT(test.erase(4) == 1); - -// TS_ASSERT(test.m_Data.size() == 5); - TS_ASSERT(test.size() == 0); - - test.erase(5);// TS_ASSERT(test.erase(5) == 0); - - test.insert(1,1); - test.insert(2,2); - test.insert(3,3); - test.insert(4,4); - - test.erase(test.begin()); -// TS_ASSERT(test.m_Data.size() == 5); - TS_ASSERT(test.size() == 3); - TS_ASSERT(test.find(1) == test.end()); - -// TS_ASSERT(test.erase(test.end()) == 0); -// TS_ASSERT(test.m_Data.back().first != INVALID_ENTITY); - } - - void test_clear() - { - EntityMap test; - test.insert(1,1); - test.insert(2,2); - test.insert(3,3); - test.insert(4,4); - - test.clear(); - -// TS_ASSERT(test.m_Data.size() == 1); - TS_ASSERT(test.size() == 0); - } - - void test_find() - { - EntityMap test; - test.insert(1,1); - test.insert(2,2); - test.insert(3,3); - test.insert(40,4); - - TS_ASSERT(test.find(1)->second == 1); - TS_ASSERT(test.find(40)->second == 4); - TS_ASSERT(test.find(30) == test.end()); - } - - void test_perf_DISABLED() - { - EntityMap test; - printf("Testing performance of EntityMap\n"); - - double t = timer_Time(); - for (int i = 1; i <= 200000; ++i) - test.insert(i,i); - double tt = timer_Time() - t; - printf("inserting 200K elements in order: %lfs\n", tt); - - t = timer_Time(); - for (int i = 1; i <= 200000; ++i) - test.erase(i); - tt = timer_Time() - t; - printf("Erasing 200K elements, by key: %lfs\n", tt); - - t = timer_Time(); - for (int i = 200000; i >= 1; --i) - test.insert(i,i); - tt = timer_Time() - t; - printf("inserting 200K elements in reverse order: %lfs\n", tt); - - t = timer_Time(); - for (auto i = test.begin(); i != test.end(); ++i) - test.erase(i); - tt = timer_Time() - t; - printf("Erasing 200K elements, by iterator: %lfs\n", tt); - - t = timer_Time(); - for (int i = 1; i <= 200000; ++i) - test.erase(i); - tt = timer_Time() - t; - printf("Erasing 200K non-existing elements: %lfs\n", tt); - - // prep random vector - std::vector vec; - for (int i = 1; i <= 200000; ++i) - vec.push_back(i); - std::random_shuffle(vec.begin(), vec.end()); - - for (int i = 1; i <= 200000; ++i) - test.insert(i,i); - - t = timer_Time(); - for (int i = 1; i <= 200000; ++i) - test.find(vec[i])->second = 3; - tt = timer_Time() - t; - printf("200K random lookups in random order: %lfs\n", tt); - - t = timer_Time(); - for (auto& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 200K continuous entitymap: %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 200000; ++i) - test.insert(i*5,i); - - t = timer_Time(); - for (EntityMap::value_type& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 200K sparse (holes of 5): %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 4000; ++i) - test.insert(i*50,i); - - t = timer_Time(); - for (EntityMap::value_type& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 4K sparse (holes of 50): %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 200000; ++i) - test.insert(i*50,i); - - t = timer_Time(); - for (EntityMap::value_type& p : test) - p.second = 3; - tt = timer_Time() - t; - printf("auto iteration on 200K sparse (holes of 50): %lfs\n", tt); - - test.clear(); - - for (int i = 1; i <= 2000000; ++i) - test.insert(i*50,i); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 1): %lfs\n", tt); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual ++iteration on 2000K sparse (holes of 50) (warmup 2): %lfs\n", tt); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual ++iteration on 2000K sparse (holes of 50): %lfs\n", tt); - - t = timer_Time(); - for (EntityMap::iterator i = test.begin(); i != test.end(); ++i) - i->second = 3; - tt = timer_Time() - t; - printf("manual iteration++ on 2000K sparse (holes of 50): %lfs\n", tt); - } -}; Index: source/simulation2/tests/test_Simulation2.h =================================================================== --- source/simulation2/tests/test_Simulation2.h +++ source/simulation2/tests/test_Simulation2.h @@ -97,14 +97,26 @@ sim.DestroyEntity(ent2); // mark it for deletion + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent1, IID_Test1))->GetX(), 999); + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent1, IID_Test2))->GetX(), 12345); + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent2, IID_Test1))->GetX(), 999); TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent2, IID_Test2))->GetX(), 12345); + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent3, IID_Test1))->GetX(), 999); + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent3, IID_Test2))->GetX(), 12345); + sim.FlushDestroyedEntities(); // actually delete it TS_ASSERT(sim.QueryInterface(ent2, IID_Test1) == NULL); TS_ASSERT(sim.QueryInterface(ent2, IID_Test2) == NULL); + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent1, IID_Test1))->GetX(), 999); + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent1, IID_Test2))->GetX(), 12345); + + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent3, IID_Test1))->GetX(), 999); + TS_ASSERT_EQUALS(static_cast (sim.QueryInterface(ent3, IID_Test2))->GetX(), 12345); + sim.FlushDestroyedEntities(); // nothing in the queue // Allow destroying INVALID_ENTITY which should do nothing. Index: source/simulation2/tests/test_SparseFlatMap.h =================================================================== --- /dev/null +++ source/simulation2/tests/test_SparseFlatMap.h @@ -0,0 +1,266 @@ +/* Copyright (C) 2017 Wildfire Games. + * This file is part of 0 A.D. + * + * 0 A.D. is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 2 of the License, or + * (at your option) any later version. + * + * 0 A.D. is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with 0 A.D. If not, see . + */ + +#include "lib/self_test.h" + +// Defines FIRST_LOCAL_ENTITY, should go before SparseFlatMap.h +#include "simulation2/system/Entity.h" + +#include "simulation2/helpers/SparseFlatMap.h" +#include "simulation2/serialization/ISerializer.h" +#include "simulation2/serialization/IDeserializer.h" + +#include "lib/timer.h" + +#include + +struct LargeStruct { + size_t a; + size_t b[100]; + LargeStruct() + { + a = 0; + } + LargeStruct(int a) + { + this->a = a; + } + bool operator==(LargeStruct o) const + { + return a == o.a; + }; + bool operator==(int o) const + { + return a == static_cast(o); + }; +}; + + +// Testing with a small and large type. +using TestMap1 = DualFlatMap; +using TestMap2 = DualFlatMap; +// No secondary ID range. +using TestMap3 = SparseFlatMap; + +class TestSparseFlatMap : public CxxTest::TestSuite +{ +public: + template + void insert_or_assign() + { + TestMap test; + + TS_ASSERT(test.empty()); + + test.insert_or_assign(1,1); + TS_ASSERT(test.insert_or_assign(2,2).second); + test.insert_or_assign(3,3); + test.insert_or_assign(4,4); + TS_ASSERT(!test.insert_or_assign(4,5).second); + test.insert_or_assign(4,6); + + TS_ASSERT(test.size() == 4); + TS_ASSERT((*test.find(3)).second == 3); + TS_ASSERT((*test.find(4)).second == 6); + + test.insert_or_assign(10,7); + TS_ASSERT(test.size() == 5); + TS_ASSERT((*test.find(4)).second == 6); + TS_ASSERT(test.find(5) == test.end()); + TS_ASSERT(test.find(6) == test.end()); + TS_ASSERT(test.find(7) == test.end()); + TS_ASSERT(test.find(8) == test.end()); + TS_ASSERT(test.find(9) == test.end()); + TS_ASSERT((*test.find(10)).second == 7); + + test.insert_or_assign(20,20); + test.insert_or_assign(11,11); + test.insert_or_assign(5,5); + + size_t iter = 0; + for (auto v : test) + iter += 1 + 0 * v.first; // use the variable to silence the warning + TS_ASSERT(iter == 8); + + // TODO: switch to if constexpr on C++17 + if (!only_first_range) + { + test.insert_or_assign(FIRST_LOCAL_ENTITY,3); + TS_ASSERT(test.size() == 9); + TS_ASSERT((*test.find(FIRST_LOCAL_ENTITY)).second == 3); + test.insert_or_assign(FIRST_LOCAL_ENTITY+1,4); + test.insert_or_assign(FIRST_LOCAL_ENTITY+2,5); + TS_ASSERT(test.size() == 11); + TS_ASSERT((*test.find(FIRST_LOCAL_ENTITY+1)).second == 4); + TS_ASSERT((*test.find(FIRST_LOCAL_ENTITY+2)).second == 5); + } + } + + template + void iterators() + { + TestMap test; + + size_t iter = 0; + for (auto v : test) + iter += v.first; // use the variable to silence the warning + + TS_ASSERT(iter == 0); + + test.insert_or_assign(1,1); + + iter = 0; + for (auto v : test) + iter += v.first; // use the variable to silence the warning + TS_ASSERT(iter == 1); + + test.insert_or_assign(2, 2); + test.insert_or_assign(3, 3); + test.insert_or_assign(4, 4); + // TODO: switch to if constexpr on C++17 + if (!only_first_range) + test.insert_or_assign(FIRST_LOCAL_ENTITY + 3, 6); + + iter = 0; + for (auto cit1 = test.begin(); cit1 != test.end(); ++cit1) + iter++; + TS_ASSERT(iter == 4 + static_cast(!only_first_range)); + + TS_ASSERT(test.find(5) == test.end()); + TS_ASSERT(test.find(3) != test.end()); + TS_ASSERT(test.find(3) == test.find(3)); + TS_ASSERT(test.find(3) != test.find(4)); + } + + template + void erase() + { + TestMap test; + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(4,4); + + TS_ASSERT(test.erase(2) == 1); + TS_ASSERT(test.size() == 3); + TS_ASSERT(test.find(2) == test.end()); + + test.erase(1); + test.erase(3); + TS_ASSERT(test.erase(4) == 1); + + TS_ASSERT(test.size() == 0); + + TS_ASSERT(test.erase(5) == 0); + + + TS_ASSERT(test.erase(250) == 0); + + TS_ASSERT(test.erase(125) == 0); + + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(4,4); + + test.erase(1); + TS_ASSERT(test.size() == 3); + TS_ASSERT(test.find(1) == test.end()); + + if (!only_first_range) + { + test.clear(); + test.insert_or_assign(4,4); + test.insert_or_assign(FIRST_LOCAL_ENTITY + 4,5); + test.erase(FIRST_LOCAL_ENTITY + 4); + TS_ASSERT(test.find(FIRST_LOCAL_ENTITY + 4) == test.end()); + TS_ASSERT(test.find(4) != test.end()); + } + } + + template + void clear() + { + TestMap test; + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(4,4); + + test.clear(); + + TS_ASSERT(test.size() == 0); + } + + template + void find() + { + TestMap test; + test.insert_or_assign(1,1); + test.insert_or_assign(2,2); + test.insert_or_assign(3,3); + test.insert_or_assign(40,4); + + typename TestMap::const_iterator it = test.find(1); + TS_ASSERT(it->first == 1); + TS_ASSERT(it != test.end()); + TS_ASSERT((*test.find(1)).second == 1); + TS_ASSERT(test.find(40)->second == 4); + TS_ASSERT(test.at(3) == 3); + TS_ASSERT(test.at(2) == 2); + TS_ASSERT(test[3] == 3); + TS_ASSERT(test[2] == 2); + TS_ASSERT(test.find(40)->second == 4); + TS_ASSERT(test.find(30) == test.end()); + + TS_ASSERT(test.find(5) == test.end()); + TS_ASSERT(test[5] == 0); + test.insert_or_assign(5, 3); + TS_ASSERT(test.at(5) == 3); + test.insert_or_assign(6, 6); + TS_ASSERT(test.at(6) == 6); + test[7] = 7; + TS_ASSERT(test.at(7) == 7); + } + + void test_small() + { + find(); + insert_or_assign(); + iterators(); + erase(); + clear(); + } + + void test_large() + { + find(); + insert_or_assign(); + iterators(); + erase(); + clear(); + } + + void test_no_secondary_ids() + { + find(); + insert_or_assign(); + iterators(); + erase(); + clear(); + } +}; Index: source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp =================================================================== --- source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp +++ source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp @@ -51,6 +51,7 @@ #include "simulation2/components/ICmpTemplateManager.h" #include "simulation2/components/ICmpVisual.h" #include "simulation2/helpers/Selection.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "ps/XML/XMLWriter.h" namespace AtlasMessage { @@ -1083,13 +1084,9 @@ player_id_t playerID = msg->player; const CSimulation2::InterfaceListUnordered& cmps = g_Game->GetSimulation2()->GetEntitiesWithInterfaceUnordered(IID_Ownership); - for (CSimulation2::InterfaceListUnordered::const_iterator eit = cmps.begin(); eit != cmps.end(); ++eit) - { - if (static_cast(eit->second)->GetOwner() == playerID) - { - ids.push_back(eit->first); - } - } + for (const std::pair& entComp : cmps) + if (static_cast(entComp.second)->GetOwner() == playerID) + ids.push_back(entComp.first); msg->ids = ids; }