Index: source/graphics/ObjectManager.cpp =================================================================== --- source/graphics/ObjectManager.cpp +++ source/graphics/ObjectManager.cpp @@ -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 auto& component : cmps) + static_cast(component.second)->Hotload(it->first); } } Index: source/simulation2/Simulation2.h =================================================================== --- source/simulation2/Simulation2.h +++ source/simulation2/Simulation2.h @@ -21,12 +21,11 @@ #include "simulation2/system/CmpPtr.h" #include "simulation2/system/Components.h" #include "simulation2/helpers/SimulationCommand.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "scriptinterface/ScriptVal.h" #include "lib/file/vfs/vfs_path.h" -#include - #include class CSimulation2Impl; @@ -207,7 +206,7 @@ void BroadcastMessage(const CMessage& msg) const; typedef std::vector > InterfaceList; - typedef boost::unordered_map InterfaceListUnordered; + typedef SparseFlatMap 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 @@ -28,6 +28,7 @@ #include "simulation2/helpers/Rasterize.h" #include "simulation2/helpers/Render.h" #include "simulation2/helpers/Spatial.h" +#include "simulation2/helpers/SparseFlatMap.h" #include "simulation2/serialization/SerializeTemplates.h" #include "graphics/Overlay.h" @@ -130,9 +131,8 @@ 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; + SparseFlatMap m_UnitShapes; + SparseFlatMap m_StaticShapes; u32 m_UnitShapeNext; // next allocated id u32 m_StaticShapeNext; @@ -184,8 +184,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 +261,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 (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 (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); } } @@ -873,7 +873,7 @@ m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); for (const entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); + SparseFlatMap::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 +889,7 @@ m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); for (const entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); + SparseFlatMap::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 +941,7 @@ m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); for (entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); + SparseFlatMap::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 +962,7 @@ m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); for (entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); + SparseFlatMap::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 +1008,7 @@ m_UnitSubdivision.GetInRange(unitShapes, posMin, posMax); for (const entity_id_t& shape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(shape); + SparseFlatMap::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 +1033,7 @@ m_StaticSubdivision.GetInRange(staticShapes, posMin, posMax); for (const entity_id_t& shape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(shape); + SparseFlatMap::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 +1162,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); + SparseFlatMap::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 +1190,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); + SparseFlatMap::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 +1227,7 @@ for (const u32& unitShape : unitShapes) { - std::map::const_iterator it = m_UnitShapes.find(unitShape); + SparseFlatMap::const_iterator it = m_UnitShapes.find(unitShape); ENSURE(it != m_UnitShapes.end()); const UnitShape& shape = it->second; @@ -1280,7 +1280,7 @@ for (const u32& staticShape : staticShapes) { - std::map::const_iterator it = m_StaticShapes.find(staticShape); + SparseFlatMap::const_iterator it = m_StaticShapes.find(staticShape); ENSURE(it != m_StaticShapes.end()); const StaticShape& shape = it->second; @@ -1324,19 +1324,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 (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 (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" @@ -235,6 +235,8 @@ cassert(sizeof(EntityData) == 24); +using EntityMap = SparseFlatMap; + /** * Serialization helper template for Query */ @@ -300,7 +302,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 +316,7 @@ return (vecA.CompareLength(vecB) < 0); } - const EntityMap& m_EntityData; + const EntityMap& m_EntityData; CFixedVector2D m_Source; private: @@ -366,7 +368,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 +461,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 +542,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 +550,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 +617,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 +651,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 +676,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 +716,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 +865,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 (std::pair& entData : m_EntityData) + if (entData.second.HasFlag()) { - if (it->second.HasFlag()) - SharingLosAdd(it->second.visionSharing, it->second.visionRange, CFixedVector2D(it->second.x, it->second.z)); + if (entData.second.HasFlag()) + SharingLosAdd(entData.second.visionSharing, entData.second.visionRange, CFixedVector2D(entData.second.x, entData.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(entData.second.owner, entData.second.visionRange, CFixedVector2D(entData.second.x, entData.second.z)); + AddToTile(PosToLosTilesHelper(entData.second.x, entData.second.z), entData.first); - if (it->second.HasFlag()) - RevealShore(it->second.owner, true); + if (entData.second.HasFlag()) + RevealShore(entData.second.owner, true); } m_TotalInworldVertices = 0; @@ -894,9 +896,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 std::pair& entData : m_EntityData) + if (entData.second.HasFlag()) + m_Subdivision.Add(entData.first, CFixedVector2D(entData.second.x, entData.second.z), entData.second.size); } virtual tag_t CreateActiveQuery(entity_id_t source, @@ -1063,11 +1065,11 @@ { std::vector entities; - for (EntityMap::const_iterator it = m_EntityData.begin(); it != m_EntityData.end(); ++it) + for (const std::pair& entData : m_EntityData) { // Check owner and add to list if it matches - if (CalcOwnerMask(it->second.owner) & ownerMask) - entities.push_back(it->first); + if (CalcOwnerMask(entData.second.owner) & ownerMask) + entities.push_back(entData.first); } return entities; @@ -1176,12 +1178,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 std::pair& entData : m_EntityData) { - if (!TestEntityQuery(q, it->first, it->second)) + if (!TestEntityQuery(q, entData.first, entData.second)) continue; - r.push_back(it->first); + r.push_back(entData.first); } } // Not the entire world, so check a parabolic range, or a regular range @@ -1197,7 +1199,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 +1237,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 +1553,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 +1581,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 +1619,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 +1715,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 +1793,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 +1959,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 std::pair& entData : m_EntityData) { - CmpPtr cmpPosition(GetSimContext(), it->first); + CmpPtr cmpPosition(GetSimContext(), entData.first); if (!cmpPosition || !cmpPosition->IsInWorld()) continue; @@ -1971,9 +1973,9 @@ if (!los.IsExplored(i,j) || los.IsVisible(i,j)) continue; - CmpPtr cmpFogging(GetSimContext(), it->first); + CmpPtr cmpFogging(GetSimContext(), entData.first); if (cmpFogging) - miragableEntities.push_back(it->first); + miragableEntities.push_back(entData.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 auto& ents : selectableEnts) { - if (CheckEntityVisibleAndInRect(it->second->GetEntityHandle(), cmpRangeManager, camera, sx0, sy0, sx1, sy1, owner, allowEditorSelectables)) - hitEnts.push_back(it->first); + if (CheckEntityVisibleAndInRect(ents.second->GetEntityHandle(), cmpRangeManager, camera, sx0, sy0, sx1, sy1, owner, allowEditorSelectables)) + hitEnts.push_back(ents.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 auto& 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,325 @@ +/* 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 +#include +#include +#include + +#include "simulation2/serialization/ISerializer.h" +#include "simulation2/serialization/IDeserializer.h" + +/** + * SparseFlatMap is a faster replacement for std::map and std::unordered_map. + * The goal for 0 A.D. is to beat both at random access and std::map at iteration. + * Requirements of T: 0 is an "invalid" state, and T can be compared with numbers. + * Requirements of V: movable + * + * It has: + * - deterministic ordering (important to ensure network synchronicity) + * Note that the ordering is not sorted as we use the swap-and-erase idiom, but it _is_ deterministic. + * - fast insertion. + * - very fast lookup: O(1), three dereferences (one from the keys vector, two from the deque). + * - fast deletion - Swap-and-erase on the deque, irrelevant on the vector. + * - very fast iteration: as the data deque is compact, this iterates as fast as iterating on a deque. + * + * This class can handle storing entities with IDs starting at 1 and n (intended for local entities, which start at FIRST_LOCAL_ENTITY). + * This secondary range of IDs is disabled by default by passing n=0, so not using it is slightly faster. + * + * This class separates "keys" and data. This lets us have very fast lookup at some memory expense, + * and very fast iteration at the expense of sorting. + * (NB: we need the data container to guarantee it won't move. Current implementation uses std::deque carefully). + * + */ + +template +class SparseFlatMap +{ +private: + friend class TestSparseFlatMap; + +public: + + typedef T key_type; + typedef V mapped_type; + typedef std::pair value_type; + +private: + static constexpr bool USE_SECONDARY_IDS = SECONDARY_ID_START != 0; + static constexpr bool USE_SBO = sizeof(mapped_type) <= sizeof(mapped_type*); + static constexpr T FIRST_VALID_ID = 1; + + using data_value_type = std::pair; + using keys_value_type = std::pair; + + using keys_container = std::vector; + keys_container m_KeysPrimary; + keys_container m_KeysSecondary; + + using data_container = std::deque; + data_container m_Data; + + // SFINAE-out the complexity of handling two ID ranges +#define IF_SECONDARY(x) template inline typename std::enable_if::type +#define NO_SECONDARY(x) template inline typename std::enable_if::type + + IF_SECONDARY(key_type) Idx(const key_type& key) const + { + // Add 1 to leave room for the "fake" at index 0. + return key >= SECONDARY_ID_START ? key - SECONDARY_ID_START + 1 : key; + } + + NO_SECONDARY(key_type) Idx(const key_type& key) const + { + return key; + } + + IF_SECONDARY(keys_container&) Keys(const key_type& key) { return key >= SECONDARY_ID_START ? m_KeysSecondary : m_KeysPrimary; } + IF_SECONDARY(const keys_container&) Keys(const key_type& key) const { return key >= SECONDARY_ID_START ? m_KeysSecondary : m_KeysPrimary; } + NO_SECONDARY(keys_container&) Keys(const key_type&) { return m_KeysPrimary; } + NO_SECONDARY(const keys_container&) Keys(const key_type&) const { return m_KeysPrimary; } + +#undef IF_SECONDARY +#undef NO_SECONDARY + +public: + + SparseFlatMap() + { + clear(); + } + + SparseFlatMap(const SparseFlatMap& o) + { + std::copy(o.m_KeysPrimary.begin(), o.m_KeysPrimary.end(), std::back_inserter(m_KeysPrimary)); + std::copy(o.m_KeysSecondary.begin(), o.m_KeysSecondary.end(), std::back_inserter(m_KeysSecondary)); + std::copy(o.m_Data.begin(), o.m_Data.end(), std::inserter(m_Data, m_Data.begin())); + } + + SparseFlatMap& operator=(const SparseFlatMap& o) + { + SparseFlatMap tmp(o); + m_KeysPrimary.swap(tmp.m_KeysPrimary); + m_KeysSecondary.swap(tmp.m_KeysSecondary); + m_Data.swap(tmp.m_Data); + return *this; + } + + // Provide an iterator-like interface for find() and such + // only this type cannot actually iterate. + template + class pseudo_iterator + { + friend class SparseFlatMap; + 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) { return value == it.value; }; + bool operator!=(const pseudo_iterator& it) { return value != it.value; }; + bool operator==(const typename data_container::iterator&) { return value == nullptr; }; + bool operator!=(const typename data_container::iterator&) { return value != nullptr; }; + bool operator==(const typename data_container::const_iterator&) { return value == nullptr; }; + bool operator!=(const typename data_container::const_iterator&) { return value != nullptr; }; + }; + + typedef pseudo_iterator iterator; + typedef pseudo_iterator const_iterator; + + iterator it(const key_type& key) + { + return iterator(key, &Keys(key)[Idx(key)].second->second); + } + + const_iterator it(const key_type& key) const + { + return const_iterator(key, &Keys(key)[Idx(key)].second->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) + { + ENSURE(key >= T{FIRST_VALID_ID}); + + key_type idx = Idx(key); + auto& keys = Keys(key); + + if (static_cast(idx) >= keys.size() - 1) + keys.resize(idx + 2, { INVALID_ENTITY, nullptr }); + + bool inserted = false; + if (keys[idx].first == INVALID_ENTITY) + { + inserted = true; + m_Data.push_back({ key, value }); + keys[idx] = { key, &m_Data.back() }; + } + else + *keys[idx].second = { key, value }; + return { it(key), inserted }; + } + + size_t erase(const iterator& it) + { + return erase(it->first); + } + + size_t erase(const key_type& key) + { + ENSURE(key >= T{FIRST_VALID_ID}); + key_type idx = Idx(key); + auto& keys = Keys(key); + if (static_cast(idx) >= keys.size() - 1 || keys[idx].first == INVALID_ENTITY) + return 0; + + data_value_type& data = *keys[idx].second; + data.second.~V(); + data = std::move(m_Data.back()); + Keys(data.first)[Idx(data.first)].second = &data; + m_Data.pop_back(); + + keys[idx].first = INVALID_ENTITY; + return 1; + } + + void clear() + { + m_KeysPrimary.clear(); + m_KeysPrimary.reserve(4096); + for (int i = 0; i < static_cast(T{FIRST_VALID_ID}); ++i) + m_KeysPrimary.push_back({ INVALID_ENTITY, nullptr }); + m_KeysSecondary.clear(); + m_KeysSecondary.reserve(4096); + m_KeysSecondary.push_back({ INVALID_ENTITY, nullptr }); + + m_Data.clear(); + } + + mapped_type& operator[] (const key_type& k) + { + if (find(k) != end()) + return (*find(k)).second; + + // Insert a default item in a valid spot so the user may modify it. + // This has the same flaw as std::map that you may inadvertantly create an item when iterating. + return (*insert_or_assign(k, V{}).first).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) + { + if (key < T{FIRST_VALID_ID}) + return end(); + key_type idx = Idx(key); + if (static_cast(idx) < Keys(key).size() - 1 && Keys(key)[idx].first != INVALID_ENTITY) + return it(key); + return end(); + } + + const_iterator find(const key_type& key) const + { + if (key < T{FIRST_VALID_ID}) + return end(); + key_type idx = Idx(key); + if (static_cast(idx) < Keys(key).size() - 1 && Keys(key)[idx].first != INVALID_ENTITY) + return it(key); + return end(); + } +}; + +template +struct SerializeSparseFlatMap +{ + template + void operator()(ISerializer& serialize, const char* UNUSED(name), SparseFlatMap& value) + { + 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), SparseFlatMap& 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_or_assign(k, v); + } + } +}; + +#endif Index: source/simulation2/system/Component.h =================================================================== --- source/simulation2/system/Component.h +++ source/simulation2/system/Component.h @@ -42,7 +42,9 @@ } #define DEFAULT_COMPONENT_ALLOCATOR(cname) \ - static IComponent* Allocate(const ScriptInterface&, JS::HandleValue) { return new CCmp##cname(); } \ + static IComponent* Allocate(const ScriptInterface&, JS::HandleValue) {\ + return new CCmp##cname();\ + } \ static void Deallocate(IComponent* cmp) { delete static_cast (cmp); } \ virtual int GetComponentTypeId() const \ { \ Index: source/simulation2/system/ComponentManager.h =================================================================== --- source/simulation2/system/ComponentManager.h +++ source/simulation2/system/ComponentManager.h @@ -30,6 +30,7 @@ #include #include #include +#include "simulation2/helpers/SparseFlatMap.h" class IComponent; class CParamNode; @@ -272,7 +273,7 @@ typedef std::pair InterfacePair; typedef std::vector InterfaceList; - typedef boost::unordered_map InterfaceListUnordered; + typedef SparseFlatMap InterfaceListUnordered; InterfaceList GetEntitiesWithInterface(InterfaceId iid) const; const InterfaceListUnordered& GetEntitiesWithInterfaceUnordered(InterfaceId iid) const; @@ -350,22 +351,25 @@ ComponentTypeId m_CurrentComponent; // used when loading component types bool m_CurrentlyHotloading; - // TODO: some of these should be vectors + // Use SparseFlatMap for indexing since ComponentTypeId, MessageTypeId, InterfaceId all have 0 as invalid + // and this is much more efficient than using std::map or std::unordered_map + using EntityComponentMap = SparseFlatMap; + 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; + SparseFlatMap m_ComponentsByInterface; + SparseFlatMap m_ComponentsByTypeId; + SparseFlatMap > m_LocalMessageSubscriptions; + SparseFlatMap > m_GlobalMessageSubscriptions; std::map m_ComponentTypeIdsByName; std::map m_MessageTypeIdsByName; - std::map m_MessageTypeNamesById; + SparseFlatMap m_MessageTypeNamesById; std::map m_InterfaceIdsByName; std::map m_DynamicMessageSubscriptionsNonsync; std::map > m_DynamicMessageSubscriptionsNonsyncByComponent; - std::unordered_map m_ComponentCaches; + SparseFlatMap m_ComponentCaches; // TODO: maintaining both ComponentsBy* is nasty; can we get rid of one, // while keeping QueryInterface and PostMessage sufficiently efficient? Index: source/simulation2/system/ComponentManager.cpp =================================================================== --- source/simulation2/system/ComponentManager.cpp +++ source/simulation2/system/ComponentManager.cpp @@ -104,7 +104,7 @@ m_ScriptInterface.SetGlobal("INVALID_PLAYER", (int)INVALID_PLAYER); m_ScriptInterface.SetGlobal("SYSTEM_ENTITY", (int)SYSTEM_ENTITY); - m_ComponentsByInterface.resize(IID__LastNative); + m_ComponentsByInterface[IID__LastNative]; // resize ResetState(); } @@ -213,17 +213,16 @@ } // 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 (auto it = componentManager->m_LocalMessageSubscriptions.begin(); it != componentManager->m_LocalMessageSubscriptions.end(); ++it) { - std::vector& types = it->second; + std::vector& types = (*it).second; std::vector::iterator ctit = find(types.begin(), types.end(), cid); if (ctit != types.end()) types.erase(ctit); } - for (it = componentManager->m_GlobalMessageSubscriptions.begin(); it != componentManager->m_GlobalMessageSubscriptions.end(); ++it) + for (auto it = componentManager->m_GlobalMessageSubscriptions.begin(); it != componentManager->m_GlobalMessageSubscriptions.end(); ++it) { - std::vector& types = it->second; + std::vector& types = (*it).second; std::vector::iterator ctit = find(types.begin(), types.end(), cid); if (ctit != types.end()) types.erase(ctit); @@ -302,11 +301,10 @@ { // 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) + const EntityComponentMap& comps = componentManager->m_ComponentsByTypeId[cid]; + for (std::pair entComp : comps) { - JS::RootedValue instance(cx, eit->second->GetJSInstance()); + JS::RootedValue instance(cx, entComp.second->GetJSInstance()); if (!instance.isNull()) componentManager->m_ScriptInterface.SetPrototype(instance, protoVal); } @@ -349,7 +347,7 @@ // IIDs start at 1, so size+1 is the next unused one size_t id = componentManager->m_InterfaceIdsByName.size() + 1; componentManager->m_InterfaceIdsByName[name] = (InterfaceId)id; - componentManager->m_ComponentsByInterface.resize(id+1); // add one so we can index by InterfaceId + componentManager->m_ComponentsByInterface[id + 1]; // resize componentManager->m_ScriptInterface.SetGlobal(("IID_" + name).c_str(), (int)id); } @@ -392,9 +390,9 @@ 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 auto& ent : ents) + if (!ENTITY_IS_LOCAL(ent.first)) + ret.push_back(ent.first); std::sort(ret.begin(), ret.end()); return ret; } @@ -495,27 +493,23 @@ m_DynamicMessageSubscriptionsNonsyncByComponent.clear(); // Delete all IComponents - std::map >::iterator iit = m_ComponentsByTypeId.begin(); - for (; iit != m_ComponentsByTypeId.end(); ++iit) + for (std::pair componentsByType : m_ComponentsByTypeId) { - std::map::iterator eit = iit->second.begin(); - for (; eit != iit->second.end(); ++eit) + for (std::pair component : componentsByType.second) { - eit->second->Deinit(); - m_ComponentTypesById[iit->first].dealloc(eit->second); + component.second->Deinit(); + m_ComponentTypesById[componentsByType.first].dealloc(component.second); } } - - std::vector >::iterator ifcit = m_ComponentsByInterface.begin(); - for (; ifcit != m_ComponentsByInterface.end(); ++ifcit) - ifcit->clear(); + for (std::pair components : m_ComponentsByInterface) + components.second.clear(); m_ComponentsByTypeId.clear(); // Delete all SEntityComponentCaches - std::unordered_map::iterator ccit = m_ComponentCaches.begin(); - for (; ccit != m_ComponentCaches.end(); ++ccit) - free(ccit->second); + for (std::pair cache : m_ComponentCaches) + free(cache.second); + m_ComponentCaches.clear(); m_SystemEntity = CEntityHandle(); @@ -739,17 +733,15 @@ const ComponentType& ct = it->second; - ENSURE((size_t)ct.iid < m_ComponentsByInterface.size()); +// ENSURE((size_t)ct.iid < m_ComponentsByInterface.size()); - boost::unordered_map& emap1 = m_ComponentsByInterface[ct.iid]; + EntityComponentMap& 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]; - // If this is a scripted component, construct the appropriate JS object first JS::RootedValue obj(cx); if (ct.type == CT_Script) @@ -769,9 +761,11 @@ component->SetEntityHandle(ent); component->SetSimContext(m_SimContext); + EntityComponentMap& emap2 = m_ComponentsByTypeId[cid]; + // 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 +784,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); + EntityComponentMap& emap1 = m_ComponentsByInterface[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); @@ -818,8 +812,7 @@ CEntityHandle CComponentManager::LookupEntityHandle(entity_id_t ent, bool allowCreate) { - std::unordered_map::iterator it; - it = m_ComponentCaches.find(ent); + SparseFlatMap::iterator it = m_ComponentCaches.find(ent); if (it == m_ComponentCaches.end()) { if (allowCreate) @@ -923,17 +916,16 @@ FlattenDynamicSubscriptions(); // Destroy the components, and remove from m_ComponentsByTypeId: - std::map >::iterator iit = m_ComponentsByTypeId.begin(); - for (; iit != m_ComponentsByTypeId.end(); ++iit) + for (std::pair entityComponents : m_ComponentsByTypeId) { - std::map::iterator eit = iit->second.find(ent); - if (eit != iit->second.end()) + EntityComponentMap::iterator eit = entityComponents.second.find(ent); + if (eit != entityComponents.second.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; + (*eit).second->Deinit(); + RemoveComponentDynamicSubscriptions((*eit).second); + m_ComponentTypesById[entityComponents.first].dealloc((*eit).second); + entityComponents.second.erase(ent); + handle.GetComponentCache()->interfaces[m_ComponentTypesById[entityComponents.first].iid] = NULL; } } @@ -941,48 +933,38 @@ 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 (std::pair components : m_ComponentsByInterface) + components.second.erase(ent); } } } IComponent* CComponentManager::QueryInterface(entity_id_t ent, InterfaceId iid) const { - if ((size_t)iid >= m_ComponentsByInterface.size()) - { - // Invalid iid - return NULL; - } - - boost::unordered_map::const_iterator eit = m_ComponentsByInterface[iid].find(ent); - if (eit == m_ComponentsByInterface[iid].end()) + if (m_ComponentsByInterface.find(iid) == m_ComponentsByInterface.end() || + m_ComponentsByInterface.at(iid).find(ent) == m_ComponentsByInterface.at(iid).end()) { // This entity doesn't implement this interface return NULL; } - return eit->second; + return (*m_ComponentsByInterface.at(iid).find(ent)).second; } CComponentManager::InterfaceList CComponentManager::GetEntitiesWithInterface(InterfaceId iid) const { std::vector > ret; - if ((size_t)iid >= m_ComponentsByInterface.size()) + if (m_ComponentsByInterface.find(iid) == m_ComponentsByInterface.end()) { - // Invalid iid + // Invalid iid or no entities return ret; } - ret.reserve(m_ComponentsByInterface[iid].size()); + ret.reserve(m_ComponentsByInterface.at(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.at(iid)) + ret.push_back(entComp); std::sort(ret.begin(), ret.end()); // lexicographic pair comparison means this'll sort by entity ID @@ -992,13 +974,13 @@ static CComponentManager::InterfaceListUnordered g_EmptyEntityMap; const CComponentManager::InterfaceListUnordered& CComponentManager::GetEntitiesWithInterfaceUnordered(InterfaceId iid) const { - if ((size_t)iid >= m_ComponentsByInterface.size()) + if (m_ComponentsByInterface.find(iid) == m_ComponentsByInterface.end()) { - // Invalid iid + // Invalid iid or no entities return g_EmptyEntityMap; } - return m_ComponentsByInterface[iid]; + return m_ComponentsByInterface.at(iid); } void CComponentManager::PostMessage(entity_id_t ent, const CMessage& msg) @@ -1006,22 +988,20 @@ 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()); + SparseFlatMap >::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 (const ComponentTypeId& componentTypeId : (*it).second) { // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); + SparseFlatMap::const_iterator emap = m_ComponentsByTypeId.find(componentTypeId); 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()) - eit->second->HandleMessage(msg, false); + EntityComponentMap::const_iterator eit = (*emap).second.find(ent); + if (eit != (*emap).second.end()) + (*eit).second->HandleMessage(msg, false); } } @@ -1031,22 +1011,19 @@ 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()); + SparseFlatMap >::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 (const ComponentTypeId& componentTypeId : (*it).second) { // Find the component instances of this type (if any) - std::map >::const_iterator emap = m_ComponentsByTypeId.find(*ctit); + SparseFlatMap::const_iterator emap = m_ComponentsByTypeId.find(componentTypeId); 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 (std::pair component : (*emap).second) + component.second->HandleMessage(msg, false); } } @@ -1060,32 +1037,29 @@ // (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()); + SparseFlatMap>::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 (const ComponentTypeId& componentTypeId : (*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); + std::map::const_iterator it = m_ComponentTypesById.find(componentTypeId); 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); + SparseFlatMap::const_iterator emap = m_ComponentsByTypeId.find(componentTypeId); 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 (const std::pair component : (*emap).second) + component.second->HandleMessage(msg, true); } } @@ -1130,17 +1104,17 @@ std::vector componentTypes; - for (std::map::const_iterator it = m_ComponentTypesById.begin(); it != m_ComponentTypesById.end(); ++it) + for (const std::pair& componentType : m_ComponentTypesById) { schema += - "" - "" - "" + it->second.schema + "" + "" + "" + "" + componentType.second.schema + "" "" ""; - interfaceComponentTypes[it->second.iid].push_back(it->second.name); - componentTypes.push_back(it->second.name); + interfaceComponentTypes[componentType.second.iid].push_back(componentType.second.name); + componentTypes.push_back(componentType.second.name); } // Declare the implementation of each interface, for documentation Index: source/simulation2/system/ComponentManagerSerialization.cpp =================================================================== --- source/simulation2/system/ComponentManagerSerialization.cpp +++ source/simulation2/system/ComponentManagerSerialization.cpp @@ -58,15 +58,9 @@ std::map > components; //std::map names; - 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; - } - } + for (const std::pair& entityComponents : m_ComponentsByTypeId) + for (const std::pair& component : entityComponents.second) + components[component.first][entityComponents.first] = component.second; std::map >::const_iterator cit = components.begin(); for (; cit != components.end(); ++cit) @@ -109,19 +103,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 (const std::pair& entityComponents : m_ComponentsByTypeId) { // In quick mode, only check unit positions - if (quick && !(cit->first == CID_Position)) + if (quick && !(entityComponents.first == 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& component : entityComponents.second) { // Don't serialize local entities - if (ENTITY_IS_LOCAL(eit->first)) + if (ENTITY_IS_LOCAL(component.first)) continue; needsSerialization = true; @@ -131,16 +124,16 @@ if (!needsSerialization) continue; - serializer.NumberI32_Unbounded("component type id", cit->first); + serializer.NumberI32_Unbounded("component type id", entityComponents.first); - for (std::map::const_iterator eit = cit->second.begin(); eit != cit->second.end(); ++eit) + for (const std::pair& component : entityComponents.second) { // Don't serialize local entities - if (ENTITY_IS_LOCAL(eit->first)) + if (ENTITY_IS_LOCAL(component.first)) continue; - serializer.NumberU32_Unbounded("entity id", eit->first); - eit->second->Serialize(serializer); + serializer.NumberU32_Unbounded("entity id", component.first); + component.second->Serialize(serializer); } } @@ -188,21 +181,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 (const std::pair& entityComponents : m_ComponentsByTypeId) { // 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& component : entityComponents.second) { // Don't serialize local entities, and handle SYSTEM_ENTITY separately - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(component.first) || component.first == SYSTEM_ENTITY) continue; needsSerialization = true; @@ -212,24 +203,24 @@ if (needsSerialization) { numComponentTypes++; - serializedComponentTypes.insert(cit->first); + serializedComponentTypes.insert(entityComponents.first); } - if (cit->second.find(SYSTEM_ENTITY) != cit->second.end()) + if (entityComponents.second.find(SYSTEM_ENTITY) != entityComponents.second.end()) { numSystemComponentTypes++; - serializedSystemComponentTypes.insert(cit->first); + serializedSystemComponentTypes.insert(entityComponents.first); } } serializer.NumberU32_Unbounded("num system component types", numSystemComponentTypes); - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (const std::pair& entityComponents : m_ComponentsByTypeId) { - if (serializedSystemComponentTypes.find(cit->first) == serializedSystemComponentTypes.end()) + if (serializedSystemComponentTypes.find(entityComponents.first) == serializedSystemComponentTypes.end()) continue; - std::map::const_iterator ctit = m_ComponentTypesById.find(cit->first); + std::map::const_iterator ctit = m_ComponentTypesById.find(entityComponents.first); if (ctit == m_ComponentTypesById.end()) { debug_warn(L"Invalid ctit"); // this should never happen @@ -238,23 +229,23 @@ serializer.StringASCII("name", ctit->second.name, 0, 255); - std::map::const_iterator eit = cit->second.find(SYSTEM_ENTITY); - if (eit == cit->second.end()) + EntityComponentMap::const_iterator eit = entityComponents.second.find(SYSTEM_ENTITY); + if (eit == entityComponents.second.end()) { debug_warn(L"Invalid eit"); // this should never happen return false; } - eit->second->Serialize(serializer); + (*eit).second->Serialize(serializer); } serializer.NumberU32_Unbounded("num component types", numComponentTypes); - for (cit = m_ComponentsByTypeId.begin(); cit != m_ComponentsByTypeId.end(); ++cit) + for (const std::pair& entityComponents : m_ComponentsByTypeId) { - if (serializedComponentTypes.find(cit->first) == serializedComponentTypes.end()) + if (serializedComponentTypes.find(entityComponents.first) == serializedComponentTypes.end()) continue; - std::map::const_iterator ctit = m_ComponentTypesById.find(cit->first); + std::map::const_iterator ctit = m_ComponentTypesById.find(entityComponents.first); if (ctit == m_ComponentTypesById.end()) { debug_warn(L"Invalid ctit"); // this should never happen @@ -265,10 +256,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& component : entityComponents.second) { // Don't serialize local entities or SYSTEM_ENTITY - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(component.first) || component.first == SYSTEM_ENTITY) continue; numComponents++; @@ -278,14 +269,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& component : entityComponents.second) { // Don't serialize local entities or SYSTEM_ENTITY - if (ENTITY_IS_LOCAL(eit->first) || eit->first == SYSTEM_ENTITY) + if (ENTITY_IS_LOCAL(component.first) || component.first == SYSTEM_ENTITY) continue; - serializer.NumberU32_Unbounded("entity id", eit->first); - eit->second->Serialize(serializer); + serializer.NumberU32_Unbounded("entity id", component.first); + component.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_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_SparseFlatMap.h =================================================================== --- /dev/null +++ source/simulation2/tests/test_SparseFlatMap.h @@ -0,0 +1,263 @@ +/* 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 = SparseFlatMap; +using TestMap2 = SparseFlatMap; +// 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[2] == 2); + TS_ASSERT(test[1] == 1); + TS_ASSERT(test.find(40)->second == 4); + TS_ASSERT(test.find(30) == test.end()); + + TS_ASSERT(test[5] == 0); + test[5] = 3; + TS_ASSERT(test[5] == 3); + test[6] = 6; + TS_ASSERT(test.at(6) == 6); + } + + 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/DeltaArray.h =================================================================== --- source/tools/atlas/GameInterface/DeltaArray.h +++ source/tools/atlas/GameInterface/DeltaArray.h @@ -18,6 +18,8 @@ #ifndef INCLUDED_DELTAARRAY #define INCLUDED_DELTAARRAY +#include + template class DeltaArray2D { public: Index: source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp =================================================================== --- source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp +++ source/tools/atlas/GameInterface/Handlers/ObjectHandlers.cpp @@ -1083,11 +1083,11 @@ 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) + for (const auto& comp : cmps) { - if (static_cast(eit->second)->GetOwner() == playerID) + if (static_cast(comp.second)->GetOwner() == playerID) { - ids.push_back(eit->first); + ids.push_back(comp.first); } }