[Bf-blender-cvs] [50b257715f8] master: Assets: Avoid quadratic complexity when freeing asset libraries

[Julian Eisel]

Commit: 50b257715f8733233dacd92476b3cbdf65ce2dad
Author: Julian Eisel
Date:   Tue Nov 15 17:34:06 2022 +0100
Branches: master
https://developer.blender.org/rB50b257715f8733233dacd92476b3cbdf65ce2dad

Assets: Avoid quadratic complexity when freeing asset libraries

Using a vector to store assets means we have to lookup the position of
the asset to be able to remove/free it. Use a `blender::Set` instead for
(nearly?) constant time removal.

===================================================================

M	source/blender/asset_system/AS_asset_library.hh
M	source/blender/asset_system/intern/asset_library.cc

===================================================================

diff --git a/source/blender/asset_system/AS_asset_library.hh b/source/blender/asset_system/AS_asset_library.hh
index a0f1214ad39..8bc9927c198 100644
--- a/source/blender/asset_system/AS_asset_library.hh
+++ b/source/blender/asset_system/AS_asset_library.hh
@@ -8,6 +8,7 @@
 
 #include "DNA_asset_types.h"
 
+#include "BLI_set.hh"
 #include "BLI_string_ref.hh"
 #include "BLI_vector.hh"
 
@@ -90,7 +91,7 @@ struct AssetLibrary {
    * already in memory and which not. Neither do we keep track of how many parts of Blender are
    * using an asset or an asset library, which is needed to know when assets can be freed.
    */
-  Vector<std::unique_ptr<AssetRepresentation>> asset_storage_;
+  Set<std::unique_ptr<AssetRepresentation>> asset_storage_;
 
   std::optional<int> find_asset_index(const AssetRepresentation &asset);
 };
diff --git a/source/blender/asset_system/intern/asset_library.cc b/source/blender/asset_system/intern/asset_library.cc
index b52594fa20c..74b39fa7b0f 100644
--- a/source/blender/asset_system/intern/asset_library.cc
+++ b/source/blender/asset_system/intern/asset_library.cc
@@ -139,39 +139,25 @@ void AssetLibrary::refresh()
 AssetRepresentation &AssetLibrary::add_external_asset(StringRef name,
                                                       std::unique_ptr<AssetMetaData> metadata)
 {
-  asset_storage_.append(std::make_unique<AssetRepresentation>(name, std::move(metadata)));
-  return *asset_storage_.last();
+  return *asset_storage_.lookup_key_or_add(
+      std::make_unique<AssetRepresentation>(name, std::move(metadata)));
 }
 
 AssetRepresentation &AssetLibrary::add_local_id_asset(ID &id)
 {
-  asset_storage_.append(std::make_unique<AssetRepresentation>(id));
-  return *asset_storage_.last();
-}
-
-std::optional<int> AssetLibrary::find_asset_index(const AssetRepresentation &asset)
-{
-  int index = 0;
-  /* Find index of asset. */
-  for (auto &asset_uptr : asset_storage_) {
-    if (&asset == asset_uptr.get()) {
-      return index;
-    }
-    index++;
-  }
-
-  return {};
+  return *asset_storage_.lookup_key_or_add(std::make_unique<AssetRepresentation>(id));
 }
 
 bool AssetLibrary::remove_asset(AssetRepresentation &asset)
 {
-  std::optional<int> asset_index = find_asset_index(asset);
-  if (!asset_index) {
-    return false;
-  }
-
-  asset_storage_.remove_and_reorder(*asset_index);
-  return true;
+  /* Create a "fake" unique_ptr to figure out the hash for the pointed to asset representation. The
+   * standard requires that this is the same for all unique_ptr's wrapping the same address. */
+  std::unique_ptr<AssetRepresentation> fake_asset_ptr{&asset};
+
+  const bool was_removed = asset_storage_.remove_as(fake_asset_ptr);
+  /* Make sure the contained storage is not destructed. */
+  fake_asset_ptr.release();
+  return was_removed;
 }
 
 namespace {