[core] refactor updateRenderables algorithm

2 files changed, 84 insertions, 67 deletions

diff --git a/src/mbgl/algorithm/update_renderables.hpp b/src/mbgl/algorithm/update_renderables.hpp
index 8948b8eafe..22d4205d90 100644
--- a/src/mbgl/algorithm/update_renderables.hpp
+++ b/src/mbgl/algorithm/update_renderables.hpp
@@ -2,65 +2,69 @@
 
 #include <mbgl/tile/tile_id.hpp>
 
-#include <map>
+#include <set>
 
 namespace mbgl {
 namespace algorithm {
 
-namespace {
-
-template <typename DataTiles, typename Renderables>
-bool tryTile(const UnwrappedTileID& renderTileID,
-             const OverscaledTileID& dataTileID,
-             const DataTiles& dataTiles,
-             Renderables& renderables) {
-    if (renderables.find(renderTileID) == renderables.end()) {
-        const auto it = dataTiles.find(dataTileID);
-        if (it == dataTiles.end() || !it->second->isRenderable()) {
-            return false;
-        }
-
-        using Renderable = typename Renderables::mapped_type;
-        renderables.emplace(renderTileID, Renderable{ renderTileID, *it->second });
-    }
-
-    return true;
-}
-
-} // namespace
-
-template <typename Renderable, typename DataTiles, typename IdealTileIDs, typename SourceInfo>
-std::map<UnwrappedTileID, Renderable> updateRenderables(const DataTiles& dataTiles,
-                                                        const IdealTileIDs& idealTileIDs,
-                                                        const SourceInfo& info,
-                                                        const uint8_t z) {
-    std::map<UnwrappedTileID, Renderable> renderables;
+template <typename GetTileDataFn,
+          typename CreateTileDataFn,
+          typename RetainTileDataFn,
+          typename RenderTileFn,
+          typename IdealTileIDs,
+          typename SourceInfo>
+void updateRenderables(GetTileDataFn getTileData,
+                       CreateTileDataFn createTileData,
+                       RetainTileDataFn retainTileData,
+                       RenderTileFn renderTile,
+                       const IdealTileIDs& idealTileIDs,
+                       const SourceInfo& info,
+                       const uint8_t dataTileZoom) {
+    std::set<UnwrappedTileID> checked;
+    bool covered;
+    int32_t overscaledZ;
 
     // for (all in the set of ideal tiles of the source) {
-    for (const auto& renderTileID : idealTileIDs) {
-        assert(renderTileID.canonical.z >= info.minZoom);
-        assert(renderTileID.canonical.z <= info.maxZoom);
-        assert(z >= renderTileID.canonical.z);
-        const auto wrap = renderTileID.wrap;
-        const OverscaledTileID dataTileID(z, renderTileID.canonical);
+    for (const auto& idealRenderTileID : idealTileIDs) {
+        assert(idealRenderTileID.canonical.z >= info.minZoom);
+        assert(idealRenderTileID.canonical.z <= info.maxZoom);
+        assert(dataTileZoom >= idealRenderTileID.canonical.z);
+
+        const OverscaledTileID idealDataTileID(dataTileZoom, idealRenderTileID.canonical);
+        auto data = getTileData(idealDataTileID);
+        if (!data) {
+            data = createTileData(idealDataTileID);
+            assert(data);
+        }
 
         // if (source has the tile and bucket is loaded) {
-        if (!tryTile(renderTileID, dataTileID, dataTiles, renderables)) {
-            // The source doesn't have the tile, or the bucket isn't loaded.
-            bool covered = true;
-            int32_t overscaledZ = z + 1;
+        if (data->isRenderable()) {
+            retainTileData(*data);
+            renderTile(idealRenderTileID, *data);
+        } else {
+            // The tile isn't loaded yet, but retain it anyway because it's an ideal tile.
+            retainTileData(*data);
+            covered = true;
+            overscaledZ = dataTileZoom + 1;
             if (overscaledZ > info.maxZoom) {
                 // We're looking for an overzoomed child tile.
-                const auto childDataTileID = dataTileID.scaledTo(overscaledZ);
-                if (!tryTile(renderTileID, childDataTileID, dataTiles, renderables)) {
+                const auto childDataTileID = idealDataTileID.scaledTo(overscaledZ);
+                data = getTileData(childDataTileID);
+                if (data && data->isRenderable()) {
+                    retainTileData(*data);
+                    renderTile(idealRenderTileID, *data);
+                } else {
                     covered = false;
                 }
             } else {
                 // Check all four actual child tiles.
-                for (const auto& childTileID : dataTileID.canonical.children()) {
+                for (const auto& childTileID : idealDataTileID.canonical.children()) {
                     const OverscaledTileID childDataTileID(overscaledZ, childTileID);
-                    const UnwrappedTileID childRenderTileID(wrap, childTileID);
-                    if (!tryTile(childRenderTileID, childDataTileID, dataTiles, renderables)) {
+                    data = getTileData(childDataTileID);
+                    if (data && data->isRenderable()) {
+                        retainTileData(*data);
+                        renderTile(childDataTileID.unwrapTo(idealRenderTileID.wrap), *data);
+                    } else {
                         // At least one child tile doesn't exist, so we are going to look for
                         // parents as well.
                         covered = false;
@@ -70,10 +74,23 @@ std::map<UnwrappedTileID, Renderable> updateRenderables(const DataTiles& dataTil
 
             if (!covered) {
                 // We couldn't find child tiles that entirely cover the ideal tile.
-                for (overscaledZ = z - 1; overscaledZ >= info.minZoom; --overscaledZ) {
-                    const auto parentDataTileID = dataTileID.scaledTo(overscaledZ);
-                    const auto parentRenderTileID = parentDataTileID.unwrapTo(renderTileID.wrap);
-                    if (tryTile(parentRenderTileID, parentDataTileID, dataTiles, renderables)) {
+                for (overscaledZ = dataTileZoom - 1; overscaledZ >= info.minZoom; --overscaledZ) {
+                    const auto parentDataTileID = idealDataTileID.scaledTo(overscaledZ);
+                    const auto parentRenderTileID =
+                        parentDataTileID.unwrapTo(idealRenderTileID.wrap);
+
+                    if (checked.find(parentRenderTileID) != checked.end()) {
+                        // Break parent tile ascent, this route has been checked by another child
+                        // tile before.
+                        break;
+                    } else {
+                        checked.emplace(parentRenderTileID);
+                    }
+
+                    data = getTileData(parentDataTileID);
+                    if (data && data->isRenderable()) {
+                        retainTileData(*data);
+                        renderTile(parentRenderTileID, *data);
                         // Break parent tile ascent, since we found one.
                         break;
                     }
@@ -81,8 +98,6 @@ std::map<UnwrappedTileID, Renderable> updateRenderables(const DataTiles& dataTil
             }
         }
     }
-
-    return renderables;
 }
 
 } // namespace algorithm
diff --git a/src/mbgl/source/source.cpp b/src/mbgl/source/source.cpp
index 5f2b54485b..1c55b9c024 100644
--- a/src/mbgl/source/source.cpp
+++ b/src/mbgl/source/source.cpp
@@ -251,7 +251,7 @@ bool Source::update(const StyleUpdateParameters& parameters) {
         }
 
         idealTiles = util::tileCover(parameters.transformState, idealZoom);
-   }
+    }
 
     // Stores a list of all the data tiles that we're definitely going to retain. There are two
     // kinds of tiles we need: the ideal tiles determined by the tile cover. They may not yet be in
@@ -259,24 +259,26 @@ bool Source::update(const StyleUpdateParameters& parameters) {
     // we're actively using, e.g. as a replacement for tile that aren't loaded yet.
     std::set<OverscaledTileID> retain;
 
-    // Create all tiles that we definitely want to load
-    for (const auto& unwrappedTileID : idealTiles) {
-        const OverscaledTileID dataTileID(dataTileZoom, unwrappedTileID.canonical);
-        retain.emplace(dataTileID);
-
-        auto it = tileDataMap.find(dataTileID);
-        if (it == tileDataMap.end()) {
-            if (auto data = createTile(dataTileID, parameters)) {
-                it = tileDataMap.emplace(dataTileID, std::move(data)).first;
-            }
+    auto retainTileDataFn = [&retain](const TileData& tileData) -> void {
+        retain.emplace(tileData.id);
+    };
+    auto getTileDataFn = [this](const OverscaledTileID& dataTileID) -> TileData* {
+        return getTileData(dataTileID);
+    };
+    auto createTileDataFn = [this, &parameters](const OverscaledTileID& dataTileID) -> TileData* {
+        if (auto data = createTile(dataTileID, parameters)) {
+            return tileDataMap.emplace(dataTileID, std::move(data)).first->second.get();
+        } else {
+            return nullptr;
         }
-    }
-
-    tiles = algorithm::updateRenderables<Tile>(tileDataMap, idealTiles, *info, overscaledZoom);
+    };
+    auto renderTileFn = [this](const UnwrappedTileID& renderTileID, TileData& tileData) {
+        tiles.emplace(renderTileID, Tile{ renderTileID, tileData });
+    };
 
-    for (auto& pair : tiles) {
-        retain.emplace(pair.second.data.id);
-    }
+    tiles.clear();
+    algorithm::updateRenderables(getTileDataFn, createTileDataFn, retainTileDataFn, renderTileFn,
+                                 idealTiles, *info, dataTileZoom);
 
     if (type != SourceType::Raster && type != SourceType::Annotations && cache.getSize() == 0) {
         size_t conservativeCacheSize =