IDManagement: Speedup ID unique name assignment by tracking used names/basenames/suffixes

An implementation of T73412, roughly as outlined there:

Track the names that are in use, as well as base names (before
numeric suffix) plus a bit map for each base name, indicating which
numeric suffixes are already used. This is done per-Main/Library,
per-object-type.

Timings (Windows, VS2022 Release build, AMD Ryzen 5950X):

- Scene with 10k cubes, Shift+D to duplicate them all: 8.7s -> 1.9s.
  Name map memory usage for resulting 20k objects: 4.3MB.
- Importing a 2.5GB .obj file of exported Blender 3.0 splash scene
  (24k objects), using the new C++ importer: 34.2s-> 22.0s. Name map
  memory usage for resulting scene: 8.6MB.
- Importing Disney Moana USD scene (almost half a million objects):
  56min -> 10min. Name map usage: ~100MB. Blender crashes later on
  when trying to render it, in the same place in both cases, but
  that's for another day.

Reviewed By: Bastien Montagne
Differential Revision: https://developer.blender.org/D14162

1 files changed, 51 insertions, 0 deletions

diff --git a/source/blender/blenkernel/BKE_main_namemap.h b/source/blender/blenkernel/BKE_main_namemap.h
new file mode 100644
index 00000000000..d201e45a2c9
--- /dev/null
+++ b/source/blender/blenkernel/BKE_main_namemap.h
@@ -0,0 +1,51 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#pragma once
+
+/** \file
+ * \ingroup bke
+ *
+ * API to ensure name uniqueness.
+ *
+ * Main database contains the UniqueName_Map which is a cache that tracks names, base
+ * names and their suffixes currently in use. So that whenever a new name has to be
+ * assigned or validated, it can quickly ensure uniqueness and adjust the name in case
+ * of collisions.
+ *
+ * \section Function Names
+ *
+ * - `BKE_main_namemap_` Should be used for functions in this file.
+ */
+
+#include "BLI_compiler_attrs.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct ID;
+struct Main;
+struct UniqueName_Map;
+
+struct UniqueName_Map *BKE_main_namemap_create(void) ATTR_WARN_UNUSED_RESULT;
+void BKE_main_namemap_destroy(struct UniqueName_Map **r_name_map) ATTR_NONNULL();
+
+/**
+ * Ensures the given name is unique within the given ID type.
+ *
+ * In case of name collisions, the name will be adjusted to be unique.
+ *
+ * \return true if the name had to be adjusted for uniqueness.
+ */
+bool BKE_main_namemap_get_name(struct Main *bmain, struct ID *id, char *name) ATTR_NONNULL();
+
+/**
+ * Remove a given name from usage.
+ *
+ * Call this whenever deleting or renaming an object.
+ */
+void BKE_main_namemap_remove_name(struct Main *bmain, struct ID *id, const char *name)
+    ATTR_NONNULL();
+
+#ifdef __cplusplus
+}
+#endif