blender
/
blender
128
396
Fork 568
Code Issues 6.2k Pull Requests 749 Projects 19 Wiki Activity

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
This commit is contained in:
Aras Pranckevicius 2022-07-20 14:27:14 +03:00
parent 8d69c6c4e7
commit 7f8d05131a
Notes: blender-bot 2023-02-13 23:38:39 +01:00 
Referenced by commit 9ac81ed6ab, Fix corrupted blend files after issues from new name_map code.
Referenced by commit 13e17507c0, Fix crashes due to non-uniqueness in ID names in some cases.
Referenced by commit b0f9639733, Fix crash due to improper handling of new library runtime name_map data on read/write.
Referenced by issue #73359, Blender editing performance with many datablocks
18 changed files with 522 additions and 289 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

8
source/blender/blenkernel/BKE_lib_id.h
View File

@ -478,10 +478,12 @@ void BKE_lib_id_expand_local(struct Main *bmain, struct ID *id, int flags);
*
* \return true if a new name had to be created.
*/
bool BKE_id_new_name_validate(struct ListBase *lb,
bool BKE_id_new_name_validate(struct Main *bmain,
struct ListBase *lb,
struct ID *id,
const char *name,
bool do_linked_data) ATTR_NONNULL(1, 2);
bool do_linked_data) ATTR_NONNULL(1, 2, 3);
/**
* Pull an ID out of a library (make it local). Only call this for IDs that
* don't have other library users.
@ -526,7 +528,7 @@ void BKE_main_lib_objects_recalc_all(struct Main *bmain);
/**
* Only for repairing files via versioning, avoid for general use.
*/
void BKE_main_id_repair_duplicate_names_listbase(struct ListBase *lb);
void BKE_main_id_repair_duplicate_names_listbase(struct Main *bmain, struct ListBase *lb);
#define MAX_ID_FULL_NAME (64 + 64 + 3 + 1) /* 64 is MAX_ID_NAME - 2 */
#define MAX_ID_FULL_NAME_UI (MAX_ID_FULL_NAME + 3) /* Adds 'keycode' two letters at beginning. */

4
source/blender/blenkernel/BKE_main.h
View File

@ -36,6 +36,7 @@ struct IDNameLib_Map;
struct ImBuf;
struct Library;
struct MainLock;
struct UniqueName_Map;
/* Blender thumbnail, as written on file (width, height, and data as char RGBA). */
/* We pack pixel data after that struct. */
@ -193,6 +194,9 @@ typedef struct Main {
/* IDMap of IDs. Currently used when reading (expanding) libraries. */
struct IDNameLib_Map *id_map;
/* Used for efficient calculations of unique names. */
struct UniqueName_Map *name_map;
struct MainLock *lock;
} Main;

51
source/blender/blenkernel/BKE_main_namemap.h Normal file
View File

@ -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

2
source/blender/blenkernel/CMakeLists.txt
View File

@ -185,6 +185,7 @@ set(SRC
intern/linestyle.c
intern/main.c
intern/main_idmap.c
intern/main_namemap.cc
intern/mask.c
intern/mask_evaluate.c
intern/mask_rasterize.c
@ -412,6 +413,7 @@ set(SRC
BKE_linestyle.h
BKE_main.h
BKE_main_idmap.h
BKE_main_namemap.h
BKE_mask.h
BKE_material.h
BKE_mball.h

286
source/blender/blenkernel/intern/lib_id.c
View File

@ -53,6 +53,7 @@
#include "BKE_lib_query.h"
#include "BKE_lib_remap.h"
#include "BKE_main.h"
#include "BKE_main_namemap.h"
#include "BKE_node.h"
#include "BKE_rigidbody.h"
@ -186,7 +187,7 @@ void BKE_lib_id_clear_library_data(Main *bmain, ID *id, const int flags)
id->tag &= ~(LIB_TAG_INDIRECT | LIB_TAG_EXTERN);
id->flag &= ~LIB_INDIRECT_WEAK_LINK;
if (id_in_mainlist) {
if (BKE_id_new_name_validate(which_libbase(bmain, GS(id->name)), id, NULL, false)) {
if (BKE_id_new_name_validate(bmain, which_libbase(bmain, GS(id->name)), id, NULL, false)) {
bmain->is_memfile_undo_written = false;
}
}
@ -842,7 +843,7 @@ void BKE_libblock_management_main_add(Main *bmain, void *idv)
BLI_addtail(lb, id);
/* We need to allow adding extra datablocks into libraries too, e.g. to support generating new
* overrides for recursive resync. */
BKE_id_new_name_validate(lb, id, NULL, true);
BKE_id_new_name_validate(bmain, lb, id, NULL, true);
/* alphabetic insertion: is in new_id */
id->tag &= ~(LIB_TAG_NO_MAIN | LIB_TAG_NO_USER_REFCOUNT);
bmain->is_memfile_undo_written = false;
@ -865,6 +866,7 @@ void BKE_libblock_management_main_remove(Main *bmain, void *idv)
ListBase *lb = which_libbase(bmain, GS(id->name));
BKE_main_lock(bmain);
BLI_remlink(lb, id);
BKE_main_namemap_remove_name(bmain, id, id->name + 2);
id->tag |= LIB_TAG_NO_MAIN;
bmain->is_memfile_undo_written = false;
BKE_main_unlock(bmain);
@ -958,7 +960,7 @@ void BKE_main_id_flag_all(Main *bmain, const int flag, const bool value)
}
}
void BKE_main_id_repair_duplicate_names_listbase(ListBase *lb)
void BKE_main_id_repair_duplicate_names_listbase(Main *bmain, ListBase *lb)
{
int lb_len = 0;
LISTBASE_FOREACH (ID *, id, lb) {
@ -982,7 +984,7 @@ void BKE_main_id_repair_duplicate_names_listbase(ListBase *lb)
}
for (i = 0; i < lb_len; i++) {
if (!BLI_gset_add(gset, id_array[i]->name + 2)) {
BKE_id_new_name_validate(lb, id_array[i], NULL, false);
BKE_id_new_name_validate(bmain, lb, id_array[i], NULL, false);
}
}
BLI_gset_free(gset, NULL);
@ -1073,7 +1075,7 @@ void *BKE_libblock_alloc(Main *bmain, short type, const char *name, const int fl
BKE_main_lock(bmain);
BLI_addtail(lb, id);
BKE_id_new_name_validate(lb, id, name, false);
BKE_id_new_name_validate(bmain, lb, id, name, false);
bmain->is_memfile_undo_written = false;
/* alphabetic insertion: is in new_id */
BKE_main_unlock(bmain);
@ -1415,255 +1417,8 @@ void id_sort_by_name(ListBase *lb, ID *id, ID *id_sorting_hint)
#undef ID_SORT_STEP_SIZE
}
/* NOTE: this code assumes and ensures that the suffix number can never go beyond 1 billion. */
#define MAX_NUMBER 1000000000
/* We do not want to get "name.000", so minimal number is 1. */
#define MIN_NUMBER 1
/* The maximum value up to which we search for the actual smallest unused number. Beyond that
* value, we will only use the first biggest unused number, without trying to 'fill the gaps'
* in-between already used numbers... */
#define MAX_NUMBERS_IN_USE 1024
/**
* Helper building final ID name from given base_name and number.
*
* If everything goes well and we do generate a valid final ID name in given name, we return
* true. In case the final name would overflow the allowed ID name length, or given number is
* bigger than maximum allowed value, we truncate further the base_name (and given name, which is
* assumed to have the same 'base_name' part), and return false.
*/
static bool id_name_final_build(char *name, char *base_name, size_t base_name_len, int number)
{
char number_str[11]; /* Dot + nine digits + NULL terminator. */
size_t number_str_len = BLI_snprintf_rlen(number_str, ARRAY_SIZE(number_str), ".%.3d", number);
/* If the number would lead to an overflow of the maximum ID name length, we need to truncate
* the base name part and do all the number checks again. */
if (base_name_len + number_str_len >= MAX_ID_NAME - 2 || number >= MAX_NUMBER) {
if (base_name_len + number_str_len >= MAX_ID_NAME - 2) {
base_name_len = MAX_ID_NAME - 2 - number_str_len - 1;
}
else {
base_name_len--;
}
base_name[base_name_len] = '\0';
/* Code above may have generated invalid utf-8 string, due to raw truncation.
* Ensure we get a valid one now. */
base_name_len -= (size_t)BLI_str_utf8_invalid_strip(base_name, base_name_len);
/* Also truncate orig name, and start the whole check again. */
name[base_name_len] = '\0';
return false;
}
/* We have our final number, we can put it in name and exit the function. */
BLI_strncpy(name + base_name_len, number_str, number_str_len + 1);
return true;
}
/**
* Check to see if an ID name is already used, and find a new one if so.
* Return true if a new name was created (returned in name).
*
* Normally the ID that's being checked is already in the ListBase, so ID *id points at the new
* entry. The Python Library module needs to know what the name of a data-block will be before it
* is appended, in this case ID *id is NULL.
*/
static bool check_for_dupid(ListBase *lb, ID *id, char *name, ID **r_id_sorting_hint)
{
BLI_assert(strlen(name) < MAX_ID_NAME - 2);
*r_id_sorting_hint = NULL;
ID *id_test = lb->first;
bool is_name_changed = false;
if (id_test == NULL) {
return is_name_changed;
}
const short id_type = (short)GS(id_test->name);
/* Static storage of previous handled ID/name info, used to perform a quicker test and optimize
* creation of huge number of IDs using the same given base name. */
static char prev_orig_base_name[MAX_ID_NAME - 2] = {0};
static char prev_final_base_name[MAX_ID_NAME - 2] = {0};
static short prev_id_type = ID_LINK_PLACEHOLDER; /* Should never exist in actual ID list. */
static int prev_number = MIN_NUMBER - 1;
/* Initial test to check whether we can 'shortcut' the more complex loop of the main code
* below. Note that we do not do that for low numbers, as that would prevent using actual
* smallest available number in some cases, and benefits of this special case handling mostly
* show up with high numbers anyway. */
if (id_type == prev_id_type && prev_number >= MAX_NUMBERS_IN_USE &&
prev_number < MAX_NUMBER - 1 && name[0] == prev_final_base_name[0]) {
/* Get the name and number parts ("name.number"). */
char base_name[MAX_ID_NAME - 2];
int number = MIN_NUMBER;
size_t base_name_len = BLI_split_name_num(base_name, &number, name, '.');
size_t prev_final_base_name_len = strlen(prev_final_base_name);
size_t prev_orig_base_name_len = strlen(prev_orig_base_name);
if (base_name_len == prev_orig_base_name_len &&
STREQLEN(base_name, prev_orig_base_name, prev_orig_base_name_len)) {
/* Once we have ensured given base_name and original previous one are the same, we can
* check that previously used number is actually used, and that next one is free. */
/* Note that from now on, we only used previous final base name, as it might have been
* truncated from original one due to number suffix length. */
char final_name[MAX_ID_NAME - 2];
char prev_final_name[MAX_ID_NAME - 2];
BLI_strncpy(final_name, prev_final_base_name, prev_final_base_name_len + 1);
BLI_strncpy(prev_final_name, prev_final_base_name, prev_final_base_name_len + 1);
if (id_name_final_build(final_name, base_name, prev_final_base_name_len, prev_number + 1) &&
id_name_final_build(prev_final_name, base_name, prev_final_base_name_len, prev_number)) {
/* We successfully built valid final names of previous and current iterations,
* now we have to ensure that previous final name is indeed used in current ID list,
* and that current one is not. */
bool is_valid = false;
for (id_test = lb->first; id_test; id_test = id_test->next) {
if (id != id_test && id_test->lib == id->lib) {
if (id_test->name[2] == final_name[0] && STREQ(final_name, id_test->name + 2)) {
/* We expect final_name to not be already used, so this is a failure. */
is_valid = false;
break;
}
/* Previous final name should only be found once in the list, so if it was found
* already, no need to do a string comparison again. */
if (!is_valid && id_test->name[2] == prev_final_name[0] &&
STREQ(prev_final_name, id_test->name + 2)) {
is_valid = true;
*r_id_sorting_hint = id_test;
}
}
}
if (is_valid) {
/* Only the number changed, prev_orig_base_name, prev_final_base_name and prev_id_type
* remain the same. */
prev_number++;
strcpy(name, final_name);
return true;
}
}
}
}
/* To speed up finding smallest unused number within [0 .. MAX_NUMBERS_IN_USE - 1].
* We do not bother beyond that point. */
ID *ids_in_use[MAX_NUMBERS_IN_USE] = {NULL};
bool is_first_run = true;
while (true) {
/* Get the name and number parts ("name.number"). */
char base_name[MAX_ID_NAME - 2];
int number = MIN_NUMBER;
size_t base_name_len = BLI_split_name_num(base_name, &number, name, '.');
/* Store previous original given base name now, as we might alter it later in code below. */
if (is_first_run) {
strcpy(prev_orig_base_name, base_name);
is_first_run = false;
}
/* In case we get an insane initial number suffix in given name. */
/* NOTE: BLI_split_name_num() cannot return negative numbers, so we do not have to check for
* that here. */
if (number >= MAX_NUMBER || number < MIN_NUMBER) {
number = MIN_NUMBER;
}
bool is_orig_name_used = false;
for (id_test = lb->first; id_test; id_test = id_test->next) {
char base_name_test[MAX_ID_NAME - 2];
int number_test;
if ((id != id_test) && (id_test->lib == id->lib) && (name[0] == id_test->name[2]) &&
(ELEM(id_test->name[base_name_len + 2], '.', '\0')) &&
STREQLEN(name, id_test->name + 2, base_name_len) &&
(BLI_split_name_num(base_name_test, &number_test, id_test->name + 2, '.') ==
base_name_len)) {
/* If we did not yet encounter exact same name as the given one, check the remaining
* parts of the strings. */
if (!is_orig_name_used) {
is_orig_name_used = STREQ(name + base_name_len, id_test->name + 2 + base_name_len);
}
/* Mark number of current id_test name as used, if possible. */
if (number_test < MAX_NUMBERS_IN_USE) {
ids_in_use[number_test] = id_test;
}
/* Keep track of first largest unused number. */
if (number <= number_test) {
*r_id_sorting_hint = id_test;
number = number_test + 1;
}
}
}
/* If there is no double, we are done.
* Note however that name might have been changed (truncated) in a previous iteration
* already.
*/
if (!is_orig_name_used) {
/* Don't bother updating `prev_*` static variables here, this case is not supposed to happen
* that often, and is not straight-forward here, so just ignore and reset them to default. */
prev_id_type = ID_LINK_PLACEHOLDER;
prev_final_base_name[0] = '\0';
prev_number = MIN_NUMBER - 1;
/* Value set previously is meaningless in that case. */
*r_id_sorting_hint = NULL;
return is_name_changed;
}
/* Decide which value of number to use, either the smallest unused one if possible, or
* default to the first largest unused one we got from previous loop. */
for (int i = MIN_NUMBER; i < MAX_NUMBERS_IN_USE; i++) {
if (ids_in_use[i] == NULL) {
number = i;
if (i > 0) {
*r_id_sorting_hint = ids_in_use[i - 1];
}
break;
}
}
/* At this point, number is either the lowest unused number within
* [MIN_NUMBER .. MAX_NUMBERS_IN_USE - 1], or 1 greater than the largest used number if all
* those low ones are taken.
* We can't be bothered to look for the lowest unused number beyond
* (MAX_NUMBERS_IN_USE - 1).
*/
/* We know for wure that name will be changed. */
is_name_changed = true;
/* If id_name_final_build helper returns false, it had to truncate further given name, hence
* we have to go over the whole check again. */
if (!id_name_final_build(name, base_name, base_name_len, number)) {
/* We have to clear our list of small used numbers before we do the whole check again. */
memset(ids_in_use, 0, sizeof(ids_in_use));
continue;
}
/* Update `prev_*` static variables, in case next call is for the same type of IDs and with the
* same initial base name, we can skip a lot of above process. */
prev_id_type = id_type;
strcpy(prev_final_base_name, base_name);
prev_number = number;
return is_name_changed;
}
#undef MAX_NUMBERS_IN_USE
}
#undef MIN_NUMBER
#undef MAX_NUMBER
bool BKE_id_new_name_validate(ListBase *lb, ID *id, const char *tname, const bool do_linked_data)
bool BKE_id_new_name_validate(
struct Main *bmain, ListBase *lb, ID *id, const char *tname, const bool do_linked_data)
{
bool result = false;
char name[MAX_ID_NAME - 2];
@ -1693,22 +1448,10 @@ bool BKE_id_new_name_validate(ListBase *lb, ID *id, const char *tname, const boo
BLI_str_utf8_invalid_strip(name, strlen(name));
}
ID *id_sorting_hint = NULL;
result = check_for_dupid(lb, id, name, &id_sorting_hint);
result = BKE_main_namemap_get_name(bmain, id, name);
strcpy(id->name + 2, name);
/* This was in 2.43 and previous releases
* however all data in blender should be sorted, not just duplicate names
* sorting should not hurt, but noting just in case it alters the way other
* functions work, so sort every time. */
#if 0
if (result) {
id_sort_by_name(lb, id, id_sorting_hint);
}
#endif
id_sort_by_name(lb, id, id_sorting_hint);
id_sort_by_name(lb, id, NULL);
return result;
}
@ -2074,7 +1817,7 @@ void BLI_libblock_ensure_unique_name(Main *bmain, const char *name)
idtest = BLI_findstring(lb, name + 2, offsetof(ID, name) + 2);
if (idtest != NULL && !ID_IS_LINKED(idtest)) {
/* BKE_id_new_name_validate also takes care of sorting. */
BKE_id_new_name_validate(lb, idtest, NULL, false);
BKE_id_new_name_validate(bmain, lb, idtest, NULL, false);
bmain->is_memfile_undo_written = false;
}
}
@ -2082,8 +1825,9 @@ void BLI_libblock_ensure_unique_name(Main *bmain, const char *name)
void BKE_libblock_rename(Main *bmain, ID *id, const char *name)
{
BLI_assert(!ID_IS_LINKED(id));
BKE_main_namemap_remove_name(bmain, id, id->name + 2);
ListBase *lb = which_libbase(bmain, GS(id->name));
if (BKE_id_new_name_validate(lb, id, name, false)) {
if (BKE_id_new_name_validate(bmain, lb, id, name, false)) {
bmain->is_memfile_undo_written = false;
}
}

3
source/blender/blenkernel/intern/lib_id_delete.c
View File

@ -28,6 +28,7 @@
#include "BKE_lib_remap.h"
#include "BKE_library.h"
#include "BKE_main.h"
#include "BKE_main_namemap.h"
#include "lib_intern.h"
@ -151,6 +152,7 @@ void BKE_id_free_ex(Main *bmain, void *idv, int flag, const bool use_flag_from_i
if ((flag & LIB_ID_FREE_NO_MAIN) == 0) {
ListBase *lb = which_libbase(bmain, type);
BLI_remlink(lb, id);
BKE_main_namemap_remove_name(bmain, id, id->name + 2);
}
BKE_libblock_free_data(id, (flag & LIB_ID_FREE_NO_USER_REFCOUNT) == 0);
@ -237,6 +239,7 @@ static size_t id_delete(Main *bmain, const bool do_tagged_deletion)
/* NOTE: in case we delete a library, we also delete all its datablocks! */
if ((id->tag & tag) || (ID_IS_LINKED(id) && (id->lib->id.tag & tag))) {
BLI_remlink(lb, id);
BKE_main_namemap_remove_name(bmain, id, id->name + 2);
BLI_addtail(&tagged_deleted_ids, id);
/* Do not tag as no_main now, we want to unlink it first (lower-level ID management
* code has some specific handling of 'no main' IDs that would be a problem in that

23
source/blender/blenkernel/intern/lib_id_test.cc
View File

@ -10,6 +10,7 @@
#include "BKE_idtype.h"
#include "BKE_lib_id.h"
#include "BKE_main.h"
#include "BKE_main_namemap.h"
#include "DNA_ID.h"
#include "DNA_mesh_types.h"
@ -57,15 +58,20 @@ TEST(lib_id_main_sort, local_ids_1)
test_lib_id_main_sort_check_order({id_a, id_b, id_c});
}
static void change_lib(Main * /*bmain*/, ID *id, Library *lib)
static void change_lib(Main *bmain, ID *id, Library *lib)
{
if (id->lib == lib) {
return;
}
BKE_main_namemap_remove_name(bmain, id, id->name + 2);
id->lib = lib;
}
static void change_name(Main *bmain, ID *id, const char *name)
{
BKE_main_namemap_remove_name(bmain, id, id->name + 2);
BLI_strncpy(id->name + 2, name, MAX_NAME);
BKE_id_new_name_validate(&bmain->objects, id, nullptr, true);
BKE_id_new_name_validate(bmain, &bmain->objects, id, nullptr, true);
}
TEST(lib_id_main_sort, linked_ids_1)
@ -389,4 +395,17 @@ TEST(lib_id_main_unique_name, names_are_unique_per_id_type)
EXPECT_STREQ(id_c->name + 2, "Foo.001");
}
TEST(lib_id_main_unique_name, name_huge_number_suffix)
{
LibIDMainSortTestContext ctx;
/* Use numeric suffix that is really large: should come through
* fine, since no duplicates with other names. */
ID *id_a = static_cast<ID *>(BKE_id_new(ctx.bmain, ID_OB, "SuperLong.1234567890"));
EXPECT_STREQ(id_a->name + 2, "SuperLong.1234567890");
/* Now create with the same name again: should get 001 suffix. */
ID *id_b = static_cast<ID *>(BKE_id_new(ctx.bmain, ID_OB, "SuperLong.1234567890"));
EXPECT_STREQ(id_b->name + 2, "SuperLong.001");
}
} // namespace blender::bke::tests

30
source/blender/blenkernel/intern/library.c
View File

@ -26,14 +26,26 @@
#include "BKE_lib_query.h"
#include "BKE_library.h"
#include "BKE_main.h"
#include "BKE_main_namemap.h"
#include "BKE_packedFile.h"
/* Unused currently. */
// static CLG_LogRef LOG = {.identifier = "bke.library"};
struct BlendWriter;
struct BlendDataReader;
static void library_runtime_reset(Library *lib)
{
if (lib->runtime.name_map) {
BKE_main_namemap_destroy(&lib->runtime.name_map);
}
}
static void library_free_data(ID *id)
{
Library *library = (Library *)id;
library_runtime_reset(library);
if (library->packedfile) {
BKE_packedfile_free(library->packedfile);
}
@ -61,6 +73,20 @@ static void library_foreach_path(ID *id, BPathForeachPathData *bpath_data)
}
}
static void library_blend_write(struct BlendWriter *UNUSED(writer),
ID *id,
const void *UNUSED(id_address))
{
Library *lib = (Library *)id;
library_runtime_reset(lib);
}
static void library_blend_read_data(struct BlendDataReader *UNUSED(reader), ID *id)
{
Library *lib = (Library *)id;
library_runtime_reset(lib);
}
IDTypeInfo IDType_ID_LI = {
.id_code = ID_LI,
.id_filter = FILTER_ID_LI,
@ -81,8 +107,8 @@ IDTypeInfo IDType_ID_LI = {
.foreach_path = library_foreach_path,
.owner_get = NULL,
.blend_write = NULL,
.blend_read_data = NULL,
.blend_write = library_blend_write,
.blend_read_data = library_blend_read_data,
.blend_read_lib = NULL,
.blend_read_expand = NULL,

5
source/blender/blenkernel/intern/main.c
View File

@ -24,6 +24,7 @@
#include "BKE_lib_query.h"
#include "BKE_main.h"
#include "BKE_main_idmap.h"
#include "BKE_main_namemap.h"
#include "IMB_imbuf.h"
#include "IMB_imbuf_types.h"
@ -184,6 +185,10 @@ void BKE_main_free(Main *mainvar)
BKE_main_idmap_destroy(mainvar->id_map);
}
if (mainvar->name_map) {
BKE_main_namemap_destroy(&mainvar->name_map);
}
BLI_spin_end((SpinLock *)mainvar->lock);
MEM_freeN(mainvar->lock);
MEM_freeN(mainvar);

361
source/blender/blenkernel/intern/main_namemap.cc Normal file
View File

@ -0,0 +1,361 @@
/* SPDX-License-Identifier: GPL-2.0-or-later */
/** \file
* \ingroup bke
*/
#include "BKE_idtype.h"
#include "BKE_main.h"
#include "BKE_main_namemap.h"
#include "BLI_assert.h"
#include "BLI_bitmap.h"
#include "BLI_ghash.h"
#include "BLI_listbase.h"
#include "BLI_map.hh"
#include "BLI_math_base.hh"
#include "BLI_set.hh"
#include "BLI_string_utf8.h"
#include "BLI_string_utils.h"
#include "DNA_ID.h"
#include "MEM_guardedalloc.h"
//#define DEBUG_PRINT_MEMORY_USAGE
using namespace blender;
/* Assumes and ensure that the suffix number can never go beyond 1 billion. */
#define MAX_NUMBER 1000000000
/* We do not want to get "name.000", so minimal number is 1. */
#define MIN_NUMBER 1
/**
* Helper building final ID name from given base_name and number.
*
* If everything goes well and we do generate a valid final ID name in given name, we return
* true. In case the final name would overflow the allowed ID name length, or given number is
* bigger than maximum allowed value, we truncate further the base_name (and given name, which is
* assumed to have the same 'base_name' part), and return false.
*/
static bool id_name_final_build(char *name, char *base_name, size_t base_name_len, int number)
{
char number_str[11]; /* Dot + nine digits + NULL terminator. */
size_t number_str_len = BLI_snprintf_rlen(number_str, ARRAY_SIZE(number_str), ".%.3d", number);
/* If the number would lead to an overflow of the maximum ID name length, we need to truncate
* the base name part and do all the number checks again. */
if (base_name_len + number_str_len >= MAX_NAME || number >= MAX_NUMBER) {
if (base_name_len + number_str_len >= MAX_NAME) {
base_name_len = MAX_NAME - number_str_len - 1;
}
else {
base_name_len--;
}
base_name[base_name_len] = '\0';
/* Code above may have generated invalid utf-8 string, due to raw truncation.
* Ensure we get a valid one now. */
base_name_len -= (size_t)BLI_str_utf8_invalid_strip(base_name, base_name_len);
/* Also truncate orig name, and start the whole check again. */
name[base_name_len] = '\0';
return false;
}
/* We have our final number, we can put it in name and exit the function. */
BLI_strncpy(name + base_name_len, number_str, number_str_len + 1);
return true;
}
/* Key used in set/map lookups: just a string name. */
struct UniqueName_Key {
char name[MAX_NAME];
uint64_t hash() const
{
return BLI_ghashutil_strhash_n(name, MAX_NAME);
}
bool operator==(const UniqueName_Key &o) const
{
return !BLI_ghashutil_strcmp(name, o.name);
}
};
/* Tracking of used numeric suffixes. For each base name:
*
* - Exactly track which of the lowest 1024 suffixes are in use,
* whenever there is a name collision we pick the lowest "unused"
* one. This is done with a bit map.
* - Above 1024, do not track them exactly, just track the maximum
* suffix value seen so far. Upon collision, assign number that is
* one larger.
*/
struct UniqueName_Value {
static constexpr unsigned max_exact_tracking = 1024;
BLI_BITMAP_DECLARE(mask, max_exact_tracking);
int max_value = 0;
void mark_used(int number)
{
if (number >= 0 && number < max_exact_tracking) {
BLI_BITMAP_ENABLE(mask, number);
}
if (number < MAX_NUMBER) {
math::max_inplace(max_value, number);
}
}
void mark_unused(int number)
{
if (number >= 0 && number < max_exact_tracking) {
BLI_BITMAP_DISABLE(mask, number);
}
if (number > 0 && number == max_value) {
--max_value;
}
}
bool use_if_unused(int number)
{
if (number >= 0 && number < max_exact_tracking) {
if (!BLI_BITMAP_TEST_BOOL(mask, number)) {
BLI_BITMAP_ENABLE(mask, number);
math::max_inplace(max_value, number);
return true;
}
}
return false;
}
int use_smallest_unused()
{
/* Find the smallest available one <1k.
* However we never want to pick zero ("none") suffix, even if it is
* available, e.g. if Foo.001 was used and we want to create another
* Foo.001, we should return Foo.002 and not Foo.
* So while searching, mark #0 as "used" to make sure we don't find it,
* and restore the value afterwards. */
BLI_bitmap prev_first = mask[0];
mask[0] |= 1;
int result = BLI_bitmap_find_first_unset(mask, max_exact_tracking);
if (result >= 0) {
BLI_BITMAP_ENABLE(mask, result);
math::max_inplace(max_value, result);
}
mask[0] |= prev_first & 1; /* Restore previous value of #0 bit. */
return result;
}
};
/* Tracking of names for a single ID type. */
struct UniqueName_TypeMap {
/* Set of full names that are in use. */
Set<UniqueName_Key> full_names;
/* For each base name (i.e. without numeric suffix), track the
* numeric suffixes that are in use. */
Map<UniqueName_Key, UniqueName_Value> base_name_to_num_suffix;
};
struct UniqueName_Map {
UniqueName_TypeMap type_maps[INDEX_ID_MAX];
UniqueName_TypeMap *find_by_type(short id_type)
{
int index = BKE_idtype_idcode_to_index(id_type);
return index >= 0 ? &type_maps[index] : nullptr;
}
};
struct UniqueName_Map *BKE_main_namemap_create()
{
struct UniqueName_Map *map = MEM_new<UniqueName_Map>(__func__);
return map;
}
void BKE_main_namemap_destroy(struct UniqueName_Map **r_name_map)
{
#ifdef DEBUG_PRINT_MEMORY_USAGE
int64_t size_sets = 0;
int64_t size_maps = 0;
for (const UniqueName_TypeMap &type_map : (*r_name_map)->type_maps) {
size_sets += type_map.full_names.size_in_bytes();
size_maps += type_map.base_name_to_num_suffix.size_in_bytes();
}
printf(
"NameMap memory usage: sets %.1fKB, maps %.1fKB\n", size_sets / 1024.0, size_maps / 1024.0);
#endif
MEM_delete<UniqueName_Map>(*r_name_map);
*r_name_map = nullptr;
}
static void main_namemap_populate(UniqueName_Map *name_map, struct Main *bmain, ID *ignore_id)
{
BLI_assert_msg(name_map != nullptr, "name_map should not be null");
for (UniqueName_TypeMap &type_map : name_map->type_maps) {
type_map.base_name_to_num_suffix.clear();
}
Library *library = ignore_id->lib;
ID *id;
FOREACH_MAIN_ID_BEGIN (bmain, id) {
if ((id == ignore_id) || (id->lib != library)) {
continue;
}
UniqueName_TypeMap *type_map = name_map->find_by_type(GS(id->name));
BLI_assert(type_map != nullptr);
/* Insert the full name into the set. */
UniqueName_Key key;
strncpy(key.name, id->name + 2, MAX_NAME);
type_map->full_names.add(key);
/* Get the name and number parts ("name.number"). */
int number = MIN_NUMBER;
BLI_split_name_num(key.name, &number, id->name + 2, '.');
/* Get and update the entry for this base name. */
UniqueName_Value &val = type_map->base_name_to_num_suffix.lookup_or_add_default(key);
val.mark_used(number);
}
FOREACH_MAIN_ID_END;
}
/* Get the name map object used for the given Main/ID.
* Lazily creates and populates the contents of the name map, if ensure_created is true.
* Note: if the contents are populated, the name of the given ID itself is not added. */
static UniqueName_Map *get_namemap_for(Main *bmain, ID *id, bool ensure_created)
{
if (id->lib != nullptr) {
if (ensure_created && id->lib->runtime.name_map == nullptr) {
id->lib->runtime.name_map = BKE_main_namemap_create();
main_namemap_populate(id->lib->runtime.name_map, bmain, id);
}
return id->lib->runtime.name_map;
}
if (ensure_created && bmain->name_map == nullptr) {
bmain->name_map = BKE_main_namemap_create();
main_namemap_populate(bmain->name_map, bmain, id);
}
return bmain->name_map;
}
bool BKE_main_namemap_get_name(struct Main *bmain, struct ID *id, char *name)
{
BLI_assert(bmain != nullptr);
BLI_assert(id != nullptr);
UniqueName_Map *name_map = get_namemap_for(bmain, id, true);
BLI_assert(name_map != nullptr);
BLI_assert(strlen(name) < MAX_NAME);
UniqueName_TypeMap *type_map = name_map->find_by_type(GS(id->name));
BLI_assert(type_map != nullptr);
bool is_name_changed = false;
UniqueName_Key key;
while (true) {
/* Check if the full original name has a duplicate. */
strncpy(key.name, name, MAX_NAME);
const bool has_dup = type_map->full_names.contains(key);
/* Get the name and number parts ("name.number"). */
int number = MIN_NUMBER;
size_t base_name_len = BLI_split_name_num(key.name, &number, name, '.');
bool added_new = false;
UniqueName_Value &val = type_map->base_name_to_num_suffix.lookup_or_add_cb(key, [&]() {
added_new = true;
return UniqueName_Value();
});
if (added_new || !has_dup) {
/* This base name is not used at all yet, or the full original
* name has no duplicates. The latter could happen if splitting
* by number would produce the same values, for different name
* strings (e.g. Foo.001 and Foo.1). */
val.mark_used(number);
if (!has_dup) {
strncpy(key.name, name, MAX_NAME);
type_map->full_names.add(key);
}
return is_name_changed;
}
/* The base name is already used. But our number suffix might not be used yet. */
int number_to_use = -1;
if (val.use_if_unused(number)) {
/* Our particular number suffix is not used yet: use it. */
number_to_use = number;
}
else {
/* Find lowest free under 1k and use it. */
number_to_use = val.use_smallest_unused();
/* Did not find one under 1k. */
if (number_to_use == -1) {
if (number >= MIN_NUMBER && number > val.max_value) {
val.max_value = number;
number_to_use = number;
}
else {
val.max_value++;
number_to_use = val.max_value;
}
}
}
/* Try to build final name from the current base name and the number.
* Note that this can fail due to too long base name, or a too large number,
* in which case it will shorten the base name, and we'll start again. */
BLI_assert(number_to_use >= MIN_NUMBER);
if (id_name_final_build(name, key.name, base_name_len, number_to_use)) {
/* All good, add final name to the set. */
strncpy(key.name, name, MAX_NAME);
type_map->full_names.add(key);
break;
}
/* Name had to be truncated, or number too large: mark
* the output name as definitely changed, and proceed with the
* truncated name again. */
is_name_changed = true;
}
return is_name_changed;
}
void BKE_main_namemap_remove_name(struct Main *bmain, struct ID *id, const char *name)
{
BLI_assert(bmain != nullptr);
BLI_assert(id != nullptr);
BLI_assert(name != nullptr);
/* Name is empty or not initialized yet, nothing to remove. */
if (name[0] == '\0') {
return;
}
struct UniqueName_Map *name_map = get_namemap_for(bmain, id, false);
if (name_map == nullptr) {
return;
}
BLI_assert(strlen(name) < MAX_NAME);
UniqueName_TypeMap *type_map = name_map->find_by_type(GS(id->name));
BLI_assert(type_map != nullptr);
UniqueName_Key key;
/* Remove full name from the set. */
strncpy(key.name, name, MAX_NAME);
type_map->full_names.remove(key);
int number = MIN_NUMBER;
BLI_split_name_num(key.name, &number, name, '.');
UniqueName_Value *val = type_map->base_name_to_num_suffix.lookup_ptr(key);
if (val == nullptr) {
return;
}
if (number == 0 && val->max_value == 0) {
/* This was the only base name usage, remove whole key. */
type_map->base_name_to_num_suffix.remove(key);
return;
}
val->mark_unused(number);
}

12
source/blender/blenloader/intern/versioning_250.c
View File

@ -425,14 +425,14 @@ static void do_versions_windowmanager_2_50(bScreen *screen)
}
}
static void versions_gpencil_add_main(ListBase *lb, ID *id, const char *name)
static void versions_gpencil_add_main(Main *bmain, ListBase *lb, ID *id, const char *name)
{
BLI_addtail(lb, id);
id->us = 1;
id->flag = LIB_FAKEUSER;
*((short *)id->name) = ID_GD;
BKE_id_new_name_validate(lb, id, name, false);
BKE_id_new_name_validate(bmain, lb, id, name, false);
/* alphabetic insertion: is in BKE_id_new_name_validate */
if ((id->tag & LIB_TAG_TEMP_MAIN) == 0) {
@ -455,21 +455,21 @@ static void do_versions_gpencil_2_50(Main *main, bScreen *screen)
if (sl->spacetype == SPACE_VIEW3D) {
View3D *v3d = (View3D *)sl;
if (v3d->gpd) {
versions_gpencil_add_main(&main->gpencils, (ID *)v3d->gpd, "GPencil View3D");
versions_gpencil_add_main(main, &main->gpencils, (ID *)v3d->gpd, "GPencil View3D");
v3d->gpd = NULL;
}
}
else if (sl->spacetype == SPACE_NODE) {
SpaceNode *snode = (SpaceNode *)sl;
if (snode->gpd) {
versions_gpencil_add_main(&main->gpencils, (ID *)snode->gpd, "GPencil Node");
versions_gpencil_add_main(main, &main->gpencils, (ID *)snode->gpd, "GPencil Node");
snode->gpd = NULL;
}
}
else if (sl->spacetype == SPACE_SEQ) {
SpaceSeq *sseq = (SpaceSeq *)sl;
if (sseq->gpd) {
versions_gpencil_add_main(&main->gpencils, (ID *)sseq->gpd, "GPencil Node");
versions_gpencil_add_main(main, &main->gpencils, (ID *)sseq->gpd, "GPencil Node");
sseq->gpd = NULL;
}
}
@ -477,7 +477,7 @@ static void do_versions_gpencil_2_50(Main *main, bScreen *screen)
SpaceImage *sima = (SpaceImage *)sl;
#if 0 /* see comment on r28002 */
if (sima->gpd) {
versions_gpencil_add_main(&main->gpencil, (ID *)sima->gpd, "GPencil Image");
versions_gpencil_add_main(main, &main->gpencil, (ID *)sima->gpd, "GPencil Image");
sima->gpd = NULL;
}
#else

2
source/blender/blenloader/intern/versioning_280.c
View File

@ -3549,7 +3549,7 @@ void blo_do_versions_280(FileData *fd, Library *UNUSED(lib), Main *bmain)
if (!MAIN_VERSION_ATLEAST(bmain, 280, 43)) {
ListBase *lb = which_libbase(bmain, ID_BR);
BKE_main_id_repair_duplicate_names_listbase(lb);
BKE_main_id_repair_duplicate_names_listbase(bmain, lb);
}
if (!MAIN_VERSION_ATLEAST(bmain, 280, 44)) {

2
source/blender/blenloader/intern/versioning_290.c
View File

@ -849,7 +849,7 @@ void blo_do_versions_290(FileData *fd, Library *UNUSED(lib), Main *bmain)
short id_codes[] = {ID_BR, ID_PAL};
for (int i = 0; i < ARRAY_SIZE(id_codes); i++) {
ListBase *lb = which_libbase(bmain, id_codes[i]);
BKE_main_id_repair_duplicate_names_listbase(lb);
BKE_main_id_repair_duplicate_names_listbase(bmain, lb);
}
}

2
source/blender/blenloader/intern/versioning_300.c
View File

@ -2017,7 +2017,7 @@ void blo_do_versions_300(FileData *fd, Library *UNUSED(lib), Main *bmain)
/* Font names were copied directly into ID names, see: T90417. */
if (!MAIN_VERSION_ATLEAST(bmain, 300, 16)) {
ListBase *lb = which_libbase(bmain, ID_VF);
BKE_main_id_repair_duplicate_names_listbase(lb);
BKE_main_id_repair_duplicate_names_listbase(bmain, lb);
}
if (!MAIN_VERSION_ATLEAST(bmain, 300, 17)) {

6
source/blender/blenloader/intern/versioning_defaults.c
View File

@ -479,8 +479,10 @@ void BLO_update_defaults_startup_blend(Main *bmain, const char *app_template)
/* Default only has one window. */
if (layout->screen) {
bScreen *screen = layout->screen;
BLI_strncpy(screen->id.name + 2, workspace->id.name + 2, sizeof(screen->id.name) - 2);
BLI_libblock_ensure_unique_name(bmain, screen->id.name);
if (!STREQ(screen->id.name + 2, workspace->id.name + 2)) {
BLI_strncpy(screen->id.name + 2, workspace->id.name + 2, sizeof(screen->id.name) - 2);
BLI_libblock_ensure_unique_name(bmain, screen->id.name);
}
}
/* For some reason we have unused screens, needed until re-saving.

4
source/blender/editors/space_outliner/outliner_draw.cc
View File

@ -37,6 +37,7 @@
#include "BKE_lib_override.h"
#include "BKE_library.h"
#include "BKE_main.h"
#include "BKE_main_namemap.h"
#include "BKE_modifier.h"
#include "BKE_node.h"
#include "BKE_object.h"
@ -677,6 +678,7 @@ static void namebutton_fn(bContext *C, void *tsep, char *oldname)
TreeElement *te = outliner_find_tree_element(&space_outliner->tree, tselem);
if (tselem->type == TSE_SOME_ID) {
BKE_main_namemap_remove_name(bmain, tselem->id, oldname);
BLI_libblock_ensure_unique_name(bmain, tselem->id->name);
WM_msg_publish_rna_prop(mbus, tselem->id, tselem->id, ID, name);
@ -742,6 +744,7 @@ static void namebutton_fn(bContext *C, void *tsep, char *oldname)
}
case TSE_NLA_ACTION: {
bAction *act = (bAction *)tselem->id;
BKE_main_namemap_remove_name(bmain, &act->id, oldname);
BLI_libblock_ensure_unique_name(bmain, act->id.name);
WM_msg_publish_rna_prop(mbus, &act->id, &act->id, ID, name);
break;
@ -852,6 +855,7 @@ static void namebutton_fn(bContext *C, void *tsep, char *oldname)
case TSE_LAYER_COLLECTION: {
/* The ID is a #Collection, not a #LayerCollection */
Collection *collection = (Collection *)tselem->id;
BKE_main_namemap_remove_name(bmain, &collection->id, oldname);
BLI_libblock_ensure_unique_name(bmain, collection->id.name);
WM_msg_publish_rna_prop(mbus, &collection->id, &collection->id, ID, name);
WM_event_add_notifier(C, NC_ID | NA_RENAME, nullptr);

8
source/blender/makesdna/DNA_ID.h
View File

@ -22,6 +22,7 @@ struct GPUTexture;
struct ID;
struct Library;
struct PackedFile;
struct UniqueName_Map;
/* Runtime display data */
struct DrawData;
@ -444,6 +445,11 @@ typedef struct ID {
struct ID_Runtime runtime;
} ID;
typedef struct Library_Runtime {
/* Used for efficient calculations of unique names. */
struct UniqueName_Map *name_map;
} Library_Runtime;
/**
* For each library file used, a Library struct is added to Main
* WARNING: readfile.c, expand_doit() reads this struct without DNA check!
@ -476,6 +482,8 @@ typedef struct Library {
int temp_index;
/** See BLENDER_FILE_VERSION, BLENDER_FILE_SUBVERSION, needed for do_versions. */
short versionfile, subversionfile;
struct Library_Runtime runtime;
} Library;
/** #Library.tag */

2
source/blender/makesrna/intern/rna_ID.c
View File

@ -16,6 +16,7 @@
#include "BKE_icons.h"
#include "BKE_lib_id.h"
#include "BKE_main_namemap.h"
#include "BKE_object.h"
#include "RNA_access.h"
@ -273,6 +274,7 @@ int rna_ID_name_length(PointerRNA *ptr)
void rna_ID_name_set(PointerRNA *ptr, const char *value)
{
ID *id = (ID *)ptr->data;
BKE_main_namemap_remove_name(G_MAIN, id, id->name + 2);
BLI_strncpy_utf8(id->name + 2, value, sizeof(id->name) - 2);
BLI_assert(BKE_id_is_in_global_main(id));
BLI_libblock_ensure_unique_name(G_MAIN, id->name);