[core] Eliminate SpriteAtlas::updateDirty

Simplify internal datastructures. Properly remove rects from the bin pack when an image is removed.

5 files changed, 112 insertions, 104 deletions

diff --git a/src/mbgl/annotation/annotation_manager.cpp b/src/mbgl/annotation/annotation_manager.cpp
index fbc0469c21..ed1518fb7b 100644
--- a/src/mbgl/annotation/annotation_manager.cpp
+++ b/src/mbgl/annotation/annotation_manager.cpp
@@ -222,12 +222,10 @@ void AnnotationManager::removeTile(AnnotationTile& tile) {
 
 void AnnotationManager::addIcon(const std::string& name, std::shared_ptr<const SpriteImage> sprite) {
     spriteAtlas.setSprite(name, sprite);
-    spriteAtlas.updateDirty();
 }
 
 void AnnotationManager::removeIcon(const std::string& name) {
     spriteAtlas.removeSprite(name);
-    spriteAtlas.updateDirty();
 }
 
 double AnnotationManager::getTopOffsetPixelsForIcon(const std::string& name) {
diff --git a/src/mbgl/map/map.cpp b/src/mbgl/map/map.cpp
index bd69ce50f4..2837a95bc5 100644
--- a/src/mbgl/map/map.cpp
+++ b/src/mbgl/map/map.cpp
@@ -924,8 +924,6 @@ void Map::addImage(const std::string& name, std::unique_ptr<const SpriteImage> i
 
     impl->styleMutated = true;
     impl->style->spriteAtlas->setSprite(name, std::move(image));
-    impl->style->spriteAtlas->updateDirty();
-
     impl->onUpdate(Update::Repaint);
 }
 
@@ -936,8 +934,6 @@ void Map::removeImage(const std::string& name) {
 
     impl->styleMutated = true;
     impl->style->spriteAtlas->removeSprite(name);
-    impl->style->spriteAtlas->updateDirty();
-
     impl->onUpdate(Update::Repaint);
 }
 
diff --git a/src/mbgl/sprite/sprite_atlas.cpp b/src/mbgl/sprite/sprite_atlas.cpp
index bd964217db..606ad4f9b8 100644
--- a/src/mbgl/sprite/sprite_atlas.cpp
+++ b/src/mbgl/sprite/sprite_atlas.cpp
@@ -102,56 +102,72 @@ void SpriteAtlas::dumpDebugLogs() const {
 }
 
 void SpriteAtlas::setSprites(const Sprites& newSprites) {
-    std::lock_guard<std::mutex> lock(mutex);
+    std::lock_guard<std::recursive_mutex> lock(mutex);
     for (const auto& pair : newSprites) {
         _setSprite(pair.first, pair.second);
     }
 }
 
 void SpriteAtlas::setSprite(const std::string& name, std::shared_ptr<const SpriteImage> sprite) {
-    std::lock_guard<std::mutex> lock(mutex);
+    std::lock_guard<std::recursive_mutex> lock(mutex);
     _setSprite(name, sprite);
 }
 
 void SpriteAtlas::removeSprite(const std::string& name) {
-    std::lock_guard<std::mutex> lock(mutex);
-    _setSprite(name);
+    std::lock_guard<std::recursive_mutex> lock(mutex);
+
+    auto it = entries.find(name);
+    if (it == entries.end()) {
+        return;
+    }
+
+    Entry& entry = it->second;
+
+    if (entry.iconRect) {
+        bin.release(*entry.iconRect);
+    }
+
+    if (entry.patternRect) {
+        bin.release(*entry.patternRect);
+    }
+
+    entries.erase(it);
 }
 
 void SpriteAtlas::_setSprite(const std::string& name,
                              const std::shared_ptr<const SpriteImage>& sprite) {
-    if (sprite) {
-        auto it = sprites.find(name);
-        if (it != sprites.end()) {
-            // There is already a sprite with that name in our store.
-            if (it->second->image.size != sprite->image.size) {
-                Log::Warning(Event::Sprite, "Can't change sprite dimensions for '%s'", name.c_str());
-                return;
-            }
-            it->second = sprite;
-        } else {
-            sprites.emplace(name, sprite);
-        }
+    auto it = entries.find(name);
+    if (it == entries.end()) {
+        entries.emplace(name, Entry { sprite, {}, {} });
+        return;
+    }
 
-        // Always add/replace the value in the dirty list.
-        auto dirty_it = dirtySprites.find(name);
-        if (dirty_it != dirtySprites.end()) {
-            dirty_it->second = sprite;
-        } else {
-            dirtySprites.emplace(name, sprite);
-        }
-    } else if (sprites.erase(name) > 0) {
-        dirtySprites.emplace(name, nullptr);
+    Entry& entry = it->second;
+
+    // There is already a sprite with that name in our store.
+    if (entry.spriteImage->image.size != sprite->image.size) {
+        Log::Warning(Event::Sprite, "Can't change sprite dimensions for '%s'", name.c_str());
+        return;
+    }
+
+    entry.spriteImage = sprite;
+
+    if (entry.iconRect) {
+        copy(entry.spriteImage->image, *entry.iconRect, SpritePatternMode::Single);
+    }
+
+    if (entry.patternRect) {
+        copy(entry.spriteImage->image, *entry.patternRect, SpritePatternMode::Repeating);
     }
 }
 
 std::shared_ptr<const SpriteImage> SpriteAtlas::getSprite(const std::string& name) {
-    std::lock_guard<std::mutex> lock(mutex);
-    const auto it = sprites.find(name);
-    if (it != sprites.end()) {
-        return it->second;
+    std::lock_guard<std::recursive_mutex> lock(mutex);
+    const auto it = entries.find(name);
+    if (it != entries.end()) {
+        return it->second.spriteImage;
     } else {
-        if (!sprites.empty()) {
+        if (!entries.empty()) {
             Log::Info(Event::Sprite, "Can't find sprite named '%s'", name.c_str());
         }
         return nullptr;
@@ -181,19 +197,35 @@ Rect<uint16_t> SpriteAtlas::allocateImage(const SpriteImage& spriteImage) {
 
 optional<SpriteAtlasElement> SpriteAtlas::getImage(const std::string& name,
                                                    const SpritePatternMode mode) {
-    std::lock_guard<std::recursive_mutex> lock(mtx);
+    std::lock_guard<std::recursive_mutex> lock(mutex);
+
+    auto it = entries.find(name);
+    if (it == entries.end()) {
+        if (!entries.empty()) {
+            Log::Info(Event::Sprite, "Can't find sprite named '%s'", name.c_str());
+        }
+        return {};
+    }
+
+    Entry& entry = it->second;
 
-    auto it = images.find({ name, mode });
-    if (it != images.end()) {
-        return it->second;
+    if (mode == SpritePatternMode::Single && entry.iconRect) {
+        return SpriteAtlasElement {
+            *entry.iconRect,
+            entry.spriteImage,
+            entry.spriteImage->pixelRatio / pixelRatio
+        };
     }
 
-    auto sprite = getSprite(name);
-    if (!sprite) {
-        return {};
+    if (mode == SpritePatternMode::Repeating && entry.patternRect) {
+        return SpriteAtlasElement {
+            *entry.patternRect,
+            entry.spriteImage,
+            entry.spriteImage->pixelRatio / pixelRatio
+        };
     }
 
-    Rect<uint16_t> rect = allocateImage(*sprite);
+    Rect<uint16_t> rect = allocateImage(*entry.spriteImage);
     if (rect.w == 0) {
         if (debug::spriteWarnings) {
             Log::Warning(Event::Sprite, "sprite atlas bitmap overflow");
@@ -201,17 +233,24 @@ optional<SpriteAtlasElement> SpriteAtlas::getImage(const std::string& name,
         return {};
     }
 
-    SpriteAtlasElement element { rect, sprite, sprite->pixelRatio / pixelRatio };
+    copy(entry.spriteImage->image, rect, mode);
 
-    images.emplace(Key{ name, mode }, element);
-    copy(sprite->image, rect, mode);
+    if (mode == SpritePatternMode::Single) {
+        entry.iconRect = rect;
+    } else {
+        entry.patternRect = rect;
+    }
 
-    return element;
+    return SpriteAtlasElement {
+        rect,
+        entry.spriteImage,
+        entry.spriteImage->pixelRatio / pixelRatio
+    };
 }
 
 optional<SpriteAtlasPosition> SpriteAtlas::getPosition(const std::string& name,
                                                        const SpritePatternMode mode) {
-    std::lock_guard<std::recursive_mutex> lock(mtx);
+    std::lock_guard<std::recursive_mutex> lock(mutex);
 
     auto img = getImage(name, mode);
     if (!img) {
@@ -263,34 +302,6 @@ void SpriteAtlas::copy(const PremultipliedImage& src, Rect<uint16_t> pos, const
     dirty = true;
 }
 
-void SpriteAtlas::updateDirty() {
-    std::lock_guard<std::recursive_mutex> lock(mtx);
-
-    auto imageIterator = images.begin();
-    auto spriteIterator = dirtySprites.begin();
-    while (imageIterator != images.end() && spriteIterator != dirtySprites.end()) {
-        if (imageIterator->first.first < spriteIterator->first) {
-            ++imageIterator;
-        } else if (spriteIterator->first < imageIterator->first.first) {
-            ++spriteIterator;
-        } else {
-            // The two names match;
-            auto& element = imageIterator->second;
-            element.spriteImage = spriteIterator->second;
-            if (element.spriteImage != nullptr) {
-                copy(element.spriteImage->image, element.pos, imageIterator->first.second);
-                ++imageIterator;
-            } else {
-                images.erase(imageIterator++);
-            }
-            // Don't advance the spriteIterator because there might be another sprite with the same
-            // name, but a different wrap value.
-        }
-    }
-
-    dirtySprites.clear();
-}
-
 void SpriteAtlas::upload(gl::Context& context, gl::TextureUnit unit) {
     if (!texture) {
         texture = context.createTexture(image, unit);
diff --git a/src/mbgl/sprite/sprite_atlas.hpp b/src/mbgl/sprite/sprite_atlas.hpp
index 9f4e20a0de..a17f35267b 100644
--- a/src/mbgl/sprite/sprite_atlas.hpp
+++ b/src/mbgl/sprite/sprite_atlas.hpp
@@ -10,7 +10,7 @@
 #include <string>
 #include <map>
 #include <mutex>
-#include <unordered_set>
+#include <unordered_map>
 #include <array>
 #include <memory>
 
@@ -85,9 +85,6 @@ public:
     // Binds the atlas texture to the GPU, and uploads data if it is out of date.
     void bind(bool linear, gl::Context&, gl::TextureUnit unit);
 
-    // Updates sprites in the atlas texture that may have changed.
-    void updateDirty();
-
     // Uploads the texture to the GPU to be available when we need it. This is a lazy operation;
     // the texture is only bound when the data is out of date (=dirty).
     void upload(gl::Context&, gl::TextureUnit unit);
@@ -104,6 +101,9 @@ private:
     void _setSprite(const std::string&, const std::shared_ptr<const SpriteImage>& = nullptr);
     void emitSpriteLoadedIfComplete();
 
+    Rect<uint16_t> allocateImage(const SpriteImage&);
+    void copy(const PremultipliedImage&, Rect<uint16_t>, SpritePatternMode);
+
     const Size size;
     const float pixelRatio;
 
@@ -114,28 +114,18 @@ private:
 
     SpriteAtlasObserver* observer = nullptr;
 
-    // Lock for sprites and dirty maps.
-    std::mutex mutex;
-
-    // Stores all current sprites.
-    Sprites sprites;
-
-    // Stores all Sprite IDs that changed since the last invocation.
-    Sprites dirtySprites;
-
-    using Key = std::pair<std::string, SpritePatternMode>;
-
-    Rect<uint16_t> allocateImage(const SpriteImage&);
-    void copy(const PremultipliedImage&, Rect<uint16_t>, SpritePatternMode);
+    struct Entry {
+        std::shared_ptr<const SpriteImage> spriteImage;
+        optional<Rect<uint16_t>> iconRect;
+        optional<Rect<uint16_t>> patternRect;
+    };
 
-    std::recursive_mutex mtx;
+    std::recursive_mutex mutex;
+    std::unordered_map<std::string, Entry> entries;
     BinPack<uint16_t> bin;
-    std::map<Key, SpriteAtlasElement> images;
-    std::unordered_set<std::string> uninitialized;
     PremultipliedImage image;
     mbgl::optional<gl::Texture> texture;
     std::atomic<bool> dirty;
-    static const int buffer = 1;
 };
 
 } // namespace mbgl
diff --git a/test/sprite/sprite_atlas.test.cpp b/test/sprite/sprite_atlas.test.cpp
index 67db917602..e84f8a9249 100644
--- a/test/sprite/sprite_atlas.test.cpp
+++ b/test/sprite/sprite_atlas.test.cpp
@@ -133,12 +133,6 @@ TEST(SpriteAtlas, Updates) {
     atlas.setSprite("one", newSprite);
     ASSERT_EQ(newSprite, atlas.getSprite("one"));
 
-    // Atlas texture hasn't changed yet.
-    test::checkImage("test/fixtures/sprite_atlas/updates_before", atlas.getAtlasImage());
-
-    atlas.updateDirty();
-
-    // Now the atlas texture has changed.
     test::checkImage("test/fixtures/sprite_atlas/updates_after", atlas.getAtlasImage());
 }
 
@@ -187,6 +181,25 @@ TEST(SpriteAtlas, AddRemove) {
     atlas.setSprite("three", sprite1);
 }
 
+TEST(SpriteAtlas, RemoveReleasesBinPackRect) {
+    FixtureLog log;
+
+    SpriteAtlas atlas({ 36, 36 }, 1);
+
+    const auto big = std::make_shared<SpriteImage>(PremultipliedImage({ 32, 32 }), 1);
+
+    atlas.setSprite("big", big);
+    EXPECT_TRUE(atlas.getImage("big", SpritePatternMode::Single));
+
+    atlas.removeSprite("big");
+
+    atlas.setSprite("big", big);
+    EXPECT_TRUE(atlas.getImage("big", SpritePatternMode::Single));
+
+    EXPECT_EQ(big, atlas.getSprite("big"));
+    EXPECT_TRUE(log.empty());
+}
+
 TEST(SpriteAtlas, OtherPixelRatio) {
     FixtureLog log;