[core] refactor ClipID generation

16 files changed, 45 insertions, 52 deletions

diff --git a/src/mbgl/algorithm/generate_clip_ids.hpp b/src/mbgl/algorithm/generate_clip_ids.hpp
index d917b398af..c4d332343b 100644
--- a/src/mbgl/algorithm/generate_clip_ids.hpp
+++ b/src/mbgl/algorithm/generate_clip_ids.hpp
@@ -25,8 +25,8 @@ private:
     std::unordered_multimap<UnwrappedTileID, Leaf> pool;
 
 public:
-    template <typename Renderables>
-    void update(Renderables& renderables);
+    template <typename Renderable>
+    void update(std::vector<std::reference_wrapper<Renderable>> renderables);
 
     std::map<UnwrappedTileID, ClipID> getStencils() const;
 };
diff --git a/src/mbgl/algorithm/generate_clip_ids_impl.hpp b/src/mbgl/algorithm/generate_clip_ids_impl.hpp
index d63ba27b6b..db62214220 100644
--- a/src/mbgl/algorithm/generate_clip_ids_impl.hpp
+++ b/src/mbgl/algorithm/generate_clip_ids_impl.hpp
@@ -7,14 +7,16 @@
 namespace mbgl {
 namespace algorithm {
 
-template <typename Renderables>
-void ClipIDGenerator::update(Renderables& renderables) {
+template <typename Renderable>
+void ClipIDGenerator::update(std::vector<std::reference_wrapper<Renderable>> renderables) {
     std::size_t size = 0;
 
+    std::sort(renderables.begin(), renderables.end(),
+              [](const auto& a, const auto& b) { return a.get().id < b.get().id; });
+
     const auto end = renderables.end();
     for (auto it = renderables.begin(); it != end; it++) {
-        auto& tileID = it->first;
-        auto& renderable = it->second;
+        auto& renderable = it->get();
         if (!renderable.used) {
             continue;
         }
@@ -28,17 +30,17 @@ void ClipIDGenerator::update(Renderables& renderables) {
         // can never be children of the current wrap.
         auto child_it = std::next(it);
         const auto children_end = std::lower_bound(
-            child_it, end, UnwrappedTileID{ static_cast<int16_t>(tileID.wrap + 1), { 0, 0, 0 } },
-            [](auto& a, auto& b) { return a.first < b; });
+            child_it, end, UnwrappedTileID{ static_cast<int16_t>(renderable.id.wrap + 1), { 0, 0, 0 } },
+            [](auto& a, auto& b) { return a.get().id < b; });
         for (; child_it != children_end; ++child_it) {
-            auto& childTileID = child_it->first;
-            if (childTileID.isChildOf(tileID)) {
+            auto& childTileID = child_it->get().id;
+            if (childTileID.isChildOf(it->get().id)) {
                 leaf.add(childTileID.canonical);
             }
         }
 
         // Find a leaf with matching children.
-        for (auto its = pool.equal_range(tileID); its.first != its.second; ++its.first) {
+        for (auto its = pool.equal_range(renderable.id); its.first != its.second; ++its.first) {
             auto& existing = its.first->second;
             if (existing == leaf) {
                 leaf.clip = existing.clip;
@@ -50,7 +52,7 @@ void ClipIDGenerator::update(Renderables& renderables) {
             size++;
         }
 
-        pool.emplace(tileID, std::move(leaf));
+        pool.emplace(renderable.id, std::move(leaf));
     }
 
     if (size > 0) {
@@ -60,8 +62,8 @@ void ClipIDGenerator::update(Renderables& renderables) {
         // We are starting our count with 1 since we need at least 1 bit set to distinguish between
         // areas without any tiles whatsoever and the current area.
         uint8_t count = 1;
-        for (auto& pair : renderables) {
-            auto& renderable = pair.second;
+        for (auto& it : renderables) {
+            auto& renderable = it.get();
             if (!renderable.used) {
                 continue;
             }
diff --git a/src/mbgl/annotation/render_annotation_source.cpp b/src/mbgl/annotation/render_annotation_source.cpp
index 8fb11785fd..0d0427b7a7 100644
--- a/src/mbgl/annotation/render_annotation_source.cpp
+++ b/src/mbgl/annotation/render_annotation_source.cpp
@@ -53,7 +53,7 @@ void RenderAnnotationSource::finishRender(Painter& painter) {
     tilePyramid.finishRender(painter);
 }
 
-std::map<UnwrappedTileID, RenderTile>& RenderAnnotationSource::getRenderTiles() {
+std::vector<std::reference_wrapper<RenderTile>> RenderAnnotationSource::getRenderTiles() {
     return tilePyramid.getRenderTiles();
 }
 
diff --git a/src/mbgl/annotation/render_annotation_source.hpp b/src/mbgl/annotation/render_annotation_source.hpp
index 7231452d4f..621298a112 100644
--- a/src/mbgl/annotation/render_annotation_source.hpp
+++ b/src/mbgl/annotation/render_annotation_source.hpp
@@ -21,7 +21,7 @@ public:
     void startRender(Painter&) final;
     void finishRender(Painter&) final;
 
-    std::map<UnwrappedTileID, RenderTile>& getRenderTiles() final;
+    std::vector<std::reference_wrapper<RenderTile>> getRenderTiles() final;
 
     std::unordered_map<std::string, std::vector<Feature>>
     queryRenderedFeatures(const ScreenLineString& geometry,
diff --git a/src/mbgl/renderer/render_source.hpp b/src/mbgl/renderer/render_source.hpp
index b82547b375..9d2e74b50b 100644
--- a/src/mbgl/renderer/render_source.hpp
+++ b/src/mbgl/renderer/render_source.hpp
@@ -57,7 +57,8 @@ public:
     virtual void startRender(Painter&) = 0;
     virtual void finishRender(Painter&) = 0;
 
-    virtual std::map<UnwrappedTileID, RenderTile>& getRenderTiles() = 0;
+    // Returns an unsorted list of RenderTiles.
+    virtual std::vector<std::reference_wrapper<RenderTile>> getRenderTiles() = 0;
 
     virtual std::unordered_map<std::string, std::vector<Feature>>
     queryRenderedFeatures(const ScreenLineString& geometry,
diff --git a/src/mbgl/renderer/render_style.cpp b/src/mbgl/renderer/render_style.cpp
index 91efb6c737..bae879dca7 100644
--- a/src/mbgl/renderer/render_style.cpp
+++ b/src/mbgl/renderer/render_style.cpp
@@ -309,16 +309,12 @@ RenderData RenderStyle::getRenderData(MapDebugOptions debugOptions, float angle)
             continue;
         }
 
-        auto& renderTiles = source->getRenderTiles();
         const bool symbolLayer = layer->is<RenderSymbolLayer>();
 
-        // Sort symbol tiles in opposite y position, so tiles with overlapping
-        // symbols are drawn on top of each other, with lower symbols being
-        // drawn on top of higher symbols.
-        std::vector<std::reference_wrapper<RenderTile>> sortedTiles;
-        std::transform(renderTiles.begin(), renderTiles.end(), std::back_inserter(sortedTiles),
-                [](auto& pair) { return std::ref(pair.second); });
+        auto sortedTiles = source->getRenderTiles();
         if (symbolLayer) {
+            // Sort symbol tiles in opposite y position, so tiles with overlapping symbols are drawn
+            // on top of each other, with lower symbols being drawn on top of higher symbols.
             std::sort(sortedTiles.begin(), sortedTiles.end(),
                       [angle](const RenderTile& a, const RenderTile& b) {
                 Point<float> pa(a.id.canonical.x, a.id.canonical.y);
diff --git a/src/mbgl/renderer/render_tile.hpp b/src/mbgl/renderer/render_tile.hpp
index 6677278873..07e2d699f7 100644
--- a/src/mbgl/renderer/render_tile.hpp
+++ b/src/mbgl/renderer/render_tile.hpp
@@ -13,7 +13,7 @@ class Tile;
 class TransformState;
 class Painter;
 
-class RenderTile {
+class RenderTile final {
 public:
     RenderTile(UnwrappedTileID id_, Tile& tile_) : id(std::move(id_)), tile(tile_) {}
     RenderTile(const RenderTile&) = delete;
diff --git a/src/mbgl/renderer/sources/render_geojson_source.cpp b/src/mbgl/renderer/sources/render_geojson_source.cpp
index 2c6935b273..c45a62498d 100644
--- a/src/mbgl/renderer/sources/render_geojson_source.cpp
+++ b/src/mbgl/renderer/sources/render_geojson_source.cpp
@@ -68,7 +68,7 @@ void RenderGeoJSONSource::finishRender(Painter& painter) {
     tilePyramid.finishRender(painter);
 }
 
-std::map<UnwrappedTileID, RenderTile>& RenderGeoJSONSource::getRenderTiles() {
+std::vector<std::reference_wrapper<RenderTile>> RenderGeoJSONSource::getRenderTiles() {
     return tilePyramid.getRenderTiles();
 }
 
diff --git a/src/mbgl/renderer/sources/render_geojson_source.hpp b/src/mbgl/renderer/sources/render_geojson_source.hpp
index b7c5a3fa7f..8d4154112f 100644
--- a/src/mbgl/renderer/sources/render_geojson_source.hpp
+++ b/src/mbgl/renderer/sources/render_geojson_source.hpp
@@ -25,7 +25,7 @@ public:
     void startRender(Painter&) final;
     void finishRender(Painter&) final;
 
-    std::map<UnwrappedTileID, RenderTile>& getRenderTiles() final;
+    std::vector<std::reference_wrapper<RenderTile>> getRenderTiles() final;
 
     std::unordered_map<std::string, std::vector<Feature>>
     queryRenderedFeatures(const ScreenLineString& geometry,
diff --git a/src/mbgl/renderer/sources/render_image_source.hpp b/src/mbgl/renderer/sources/render_image_source.hpp
index 88f1c56567..41c4bd5483 100644
--- a/src/mbgl/renderer/sources/render_image_source.hpp
+++ b/src/mbgl/renderer/sources/render_image_source.hpp
@@ -30,8 +30,8 @@ public:
                 bool needsRelayout,
                 const TileParameters&) final;
 
-    std::map<UnwrappedTileID, RenderTile>& getRenderTiles() final {
-        return tiles;
+    std::vector<std::reference_wrapper<RenderTile>> getRenderTiles() final {
+        return {};
     }
 
     std::unordered_map<std::string, std::vector<Feature>>
@@ -48,7 +48,6 @@ public:
 
 private:
     const style::ImageSource::Impl& impl() const;
-    std::map<UnwrappedTileID, RenderTile> tiles;
 
     std::vector<UnwrappedTileID> tileIds;
     std::unique_ptr<RasterBucket> bucket;
diff --git a/src/mbgl/renderer/sources/render_raster_source.cpp b/src/mbgl/renderer/sources/render_raster_source.cpp
index 20c148870e..2006e31628 100644
--- a/src/mbgl/renderer/sources/render_raster_source.cpp
+++ b/src/mbgl/renderer/sources/render_raster_source.cpp
@@ -64,7 +64,7 @@ void RenderRasterSource::finishRender(Painter& painter) {
     tilePyramid.finishRender(painter);
 }
 
-std::map<UnwrappedTileID, RenderTile>& RenderRasterSource::getRenderTiles() {
+std::vector<std::reference_wrapper<RenderTile>> RenderRasterSource::getRenderTiles() {
     return tilePyramid.getRenderTiles();
 }
 
diff --git a/src/mbgl/renderer/sources/render_raster_source.hpp b/src/mbgl/renderer/sources/render_raster_source.hpp
index 7d0c245e45..73a2ac3b22 100644
--- a/src/mbgl/renderer/sources/render_raster_source.hpp
+++ b/src/mbgl/renderer/sources/render_raster_source.hpp
@@ -21,7 +21,7 @@ public:
     void startRender(Painter&) final;
     void finishRender(Painter&) final;
 
-    std::map<UnwrappedTileID, RenderTile>& getRenderTiles() final;
+    std::vector<std::reference_wrapper<RenderTile>> getRenderTiles() final;
 
     std::unordered_map<std::string, std::vector<Feature>>
     queryRenderedFeatures(const ScreenLineString& geometry,
diff --git a/src/mbgl/renderer/sources/render_vector_source.cpp b/src/mbgl/renderer/sources/render_vector_source.cpp
index 4302fb21ee..0f44a64b63 100644
--- a/src/mbgl/renderer/sources/render_vector_source.cpp
+++ b/src/mbgl/renderer/sources/render_vector_source.cpp
@@ -69,7 +69,7 @@ void RenderVectorSource::finishRender(Painter& painter) {
     tilePyramid.finishRender(painter);
 }
 
-std::map<UnwrappedTileID, RenderTile>& RenderVectorSource::getRenderTiles() {
+std::vector<std::reference_wrapper<RenderTile>> RenderVectorSource::getRenderTiles() {
     return tilePyramid.getRenderTiles();
 }
 
diff --git a/src/mbgl/renderer/sources/render_vector_source.hpp b/src/mbgl/renderer/sources/render_vector_source.hpp
index 5e15fee533..231a9071ab 100644
--- a/src/mbgl/renderer/sources/render_vector_source.hpp
+++ b/src/mbgl/renderer/sources/render_vector_source.hpp
@@ -21,7 +21,7 @@ public:
     void startRender(Painter&) final;
     void finishRender(Painter&) final;
 
-    std::map<UnwrappedTileID, RenderTile>& getRenderTiles() final;
+    std::vector<std::reference_wrapper<RenderTile>> getRenderTiles() final;
 
     std::unordered_map<std::string, std::vector<Feature>>
     queryRenderedFeatures(const ScreenLineString& geometry,
diff --git a/src/mbgl/renderer/tile_pyramid.cpp b/src/mbgl/renderer/tile_pyramid.cpp
index c2806299e3..caf55d64e8 100644
--- a/src/mbgl/renderer/tile_pyramid.cpp
+++ b/src/mbgl/renderer/tile_pyramid.cpp
@@ -40,22 +40,21 @@ bool TilePyramid::isLoaded() const {
 }
 
 void TilePyramid::startRender(Painter& painter) {
-    for (auto& pair : renderTiles) {
-        pair.second.startRender(painter);
+    for (auto& tile : renderTiles) {
+        tile.startRender(painter);
     }
 }
 
 void TilePyramid::finishRender(Painter& painter) {
-    for (auto& pair : renderTiles) {
-        auto& tile = pair.second;
+    for (auto& tile : renderTiles) {
         if (tile.used) {
             painter.renderTileDebug(tile);
         }
     }
 }
 
-std::map<UnwrappedTileID, RenderTile>& TilePyramid::getRenderTiles() {
-    return renderTiles;
+std::vector<std::reference_wrapper<RenderTile>> TilePyramid::getRenderTiles() {
+    return { renderTiles.begin(), renderTiles.end() };
 }
 
 void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layers,
@@ -134,7 +133,7 @@ void TilePyramid::update(const std::vector<Immutable<style::Layer::Impl>>& layer
         return tiles.emplace(tileID, std::move(tile)).first->second.get();
     };
     auto renderTileFn = [&](const UnwrappedTileID& tileID, Tile& tile) {
-        renderTiles.emplace(tileID, RenderTile{ tileID, tile });
+        renderTiles.emplace_back(tileID, tile);
     };
 
     renderTiles.clear();
@@ -199,18 +198,14 @@ std::unordered_map<std::string, std::vector<Feature>> TilePyramid::queryRendered
 
     mapbox::geometry::box<double> box = mapbox::geometry::envelope(queryGeometry);
 
-
-    auto sortRenderTiles = [](const RenderTile& a, const RenderTile& b) {
+    std::vector<std::reference_wrapper<const RenderTile>> sortedTiles{ renderTiles.begin(),
+                                                                       renderTiles.end() };
+    std::sort(sortedTiles.begin(), sortedTiles.end(), [](const RenderTile& a, const RenderTile& b) {
         return std::tie(a.id.canonical.z, a.id.canonical.y, a.id.wrap, a.id.canonical.x) <
             std::tie(b.id.canonical.z, b.id.canonical.y, b.id.wrap, b.id.canonical.x);
-    };
-    std::vector<std::reference_wrapper<const RenderTile>> sortedTiles;
-    std::transform(renderTiles.cbegin(), renderTiles.cend(), std::back_inserter(sortedTiles),
-                   [](const auto& pair) { return std::ref(pair.second); });
-    std::sort(sortedTiles.begin(), sortedTiles.end(), sortRenderTiles);
+    });
 
-    for (const auto& renderTileRef : sortedTiles) {
-        const RenderTile& renderTile = renderTileRef.get();
+    for (const RenderTile& renderTile : sortedTiles) {
         GeometryCoordinate tileSpaceBoundsMin = TileCoordinate::toGeometryCoordinate(renderTile.id, box.min);
         if (tileSpaceBoundsMin.x >= util::EXTENT || tileSpaceBoundsMin.y >= util::EXTENT) {
             continue;
diff --git a/src/mbgl/renderer/tile_pyramid.hpp b/src/mbgl/renderer/tile_pyramid.hpp
index 5846560808..a3db65b460 100644
--- a/src/mbgl/renderer/tile_pyramid.hpp
+++ b/src/mbgl/renderer/tile_pyramid.hpp
@@ -45,7 +45,7 @@ public:
     void startRender(Painter&);
     void finishRender(Painter&);
 
-    std::map<UnwrappedTileID, RenderTile>& getRenderTiles();
+    std::vector<std::reference_wrapper<RenderTile>> getRenderTiles();
 
     std::unordered_map<std::string, std::vector<Feature>>
     queryRenderedFeatures(const ScreenLineString& geometry,
@@ -68,7 +68,7 @@ public:
     std::map<OverscaledTileID, std::unique_ptr<Tile>> tiles;
     TileCache cache;
 
-    std::map<UnwrappedTileID, RenderTile> renderTiles;
+    std::vector<RenderTile> renderTiles;
 
     TileObserver* observer = nullptr;
 };