SkFlattenable::Register now performs a sorted insert

In order to maintain the sorted quality of `Entry gEntries`, I updated SkFlattenable::Register to perform a sorted insert with the new element. To avoid possible threading issues, I added an SkSharedMutex.

Change-Id: I14a9001ef2822211bbcbe994b73b4671ae17844d
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/1252956
Reviewed-by: Kaylee Lubick <kjlubick@google.com>
Commit-Queue: Alexis Cruz-Ayala <alexisdavidc@google.com>

include/core/SkFlattenable.h

diff --git a/include/core/SkFlattenable.h b/include/core/SkFlattenable.h
index 892a593..eaa790d 100644
--- a/include/core/SkFlattenable.h
+++ b/include/core/SkFlattenable.h
@@ -86,7 +86,6 @@
 
 private:
     static void RegisterFlattenablesIfNeeded();
-    static void Finalize();
 
     friend class SkGraphics;
 

src/core/SkFlattenable.cpp

diff --git a/src/core/SkFlattenable.cpp b/src/core/SkFlattenable.cpp
index e10f54e..62642aa 100644
--- a/src/core/SkFlattenable.cpp
+++ b/src/core/SkFlattenable.cpp
@@ -11,6 +11,7 @@
 #include "include/core/SkSerialProcs.h"
 #include "include/core/SkTypes.h"
 #include "include/private/base/SkTDArray.h"
+#include "src/base/SkSharedMutex.h"
 #include "src/core/SkPtrRecorder.h"
 #include "src/core/SkReadBuffer.h"
 #include "src/core/SkWriteBuffer.h"
@@ -80,25 +81,57 @@
 };
 
 int gCount = 0;
-Entry gEntries[128];
+Entry gEntries[128] = {};
+SkSharedMutex gEntriesMutex;
 
 }  // namespace
 
-void SkFlattenable::Finalize() {
-    std::sort(gEntries, gEntries + gCount, EntryComparator());
-}
-
 void SkFlattenable::Register(const char name[], Factory factory) {
+    SkAutoSharedMutexExclusive lock(gEntriesMutex);
     SkASSERT(name);
     SkASSERT(factory);
     SkASSERT(gCount < (int)std::size(gEntries));
 
+    /**
+     * We add the new Entry to gEntries using a sorted insertion
+     *
+     * We first find the position at which we must insert the new Entry (insertion_element =
+     * std::upper_bound). Then we add our new Entry to gEntries[gCount]
+     *
+     * Then we call std::rotate(first, middle, last) to place our new Entry at the beginning of
+     * insertion_element
+     * - first will be the beginning of the elements we want to shift
+     * - middle will be the new Entry we want to insert, the things before it will get shifted
+     * - last will be the element after the one we are inserting
+     *
+     * As an example, let's insert name = 'dragonfruit' into
+     * gEntries = ['apple', 'blueberry', 'coconut', 'elderberry', 'fig'] with
+     * gCount = 5
+     *
+     * After upper_bound, insertion_element points to 'elderberry' (the first element that comes
+     * after 'dragonfruit')
+     *
+     * After gEntries[gCount] = name, gEntries + gCount points to 'dragonfruit'
+     *
+     * now we have gEntries = ['apple', 'blueberry', 'coconut', 'elderberry', 'fig', 'dragonfruit']
+     *
+     * so std::rotate('elderberry', 'dragonfruit', 'dragonfruit'+1); will result in
+     * gEntries = ['apple', 'blueberry', 'coconut', 'dragonfruit', 'elderberry', 'fig']
+     *
+     * This will effectively move the new Entry to the insertion_element position, while maintaining
+     * the order of the other elements
+     */
+    Entry* insertion_element =
+            std::upper_bound(gEntries, gEntries + gCount, name, EntryComparator());
     gEntries[gCount].fName = name;
     gEntries[gCount].fFactory = factory;
+
+    std::rotate(insertion_element, gEntries + gCount, gEntries + gCount + 1);
     gCount += 1;
 }
 
 SkFlattenable::Factory SkFlattenable::NameToFactory(const char name[]) {
+    SkAutoSharedMutexShared lock(gEntriesMutex);
     RegisterFlattenablesIfNeeded();
 
     SkASSERT(std::is_sorted(gEntries, gEntries + gCount, EntryComparator()));
@@ -110,6 +143,7 @@
 }
 
 const char* SkFlattenable::FactoryToName(Factory fact) {
+    SkAutoSharedMutexShared lock(gEntriesMutex);
     RegisterFlattenablesIfNeeded();
 
     const Entry* entries = gEntries;

src/core/SkGlobalInitialization_core.cpp

diff --git a/src/core/SkGlobalInitialization_core.cpp b/src/core/SkGlobalInitialization_core.cpp
index c189a32..e580c21 100644
--- a/src/core/SkGlobalInitialization_core.cpp
+++ b/src/core/SkGlobalInitialization_core.cpp
@@ -13,6 +13,5 @@
     once([]{
         SkFlattenable::PrivateInitializer::InitEffects();
         SkFlattenable::PrivateInitializer::InitImageFilters();
-        SkFlattenable::Finalize();
     });
 }