Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender')
-rw-r--r--source/blender/blenkernel/BKE_treehash.h52
-rw-r--r--source/blender/blenkernel/CMakeLists.txt2
-rw-r--r--source/blender/blenkernel/intern/treehash.c133
-rw-r--r--source/blender/blenlib/BLI_ghash.h2
-rw-r--r--source/blender/blenloader/intern/readfile.c19
-rw-r--r--source/blender/editors/space_outliner/outliner_tools.c5
-rw-r--r--source/blender/editors/space_outliner/outliner_tree.c66
-rw-r--r--source/blender/editors/space_outliner/space_outliner.c3
-rw-r--r--source/blender/makesdna/DNA_space_types.h7
9 files changed, 208 insertions, 81 deletions
diff --git a/source/blender/blenkernel/BKE_treehash.h b/source/blender/blenkernel/BKE_treehash.h
new file mode 100644
index 00000000000..54deef1ce2f
--- /dev/null
+++ b/source/blender/blenkernel/BKE_treehash.h
@@ -0,0 +1,52 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Blender Foundation 2013
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef __BKE_TREEHASH_H__
+#define __BKE_TREEHASH_H__
+
+/** \file BKE_treehash.h
+ * \ingroup bke
+ */
+
+struct ID;
+struct GHash;
+struct BLI_mempool;
+struct TreeStoreElem;
+
+/* create and fill hashtable with treestore elements */
+void *BKE_treehash_create_from_treestore(struct BLI_mempool *treestore);
+
+/* full rebuild for already allocated hashtable */
+void *BKE_treehash_rebuild_from_treestore(void *treehash, struct BLI_mempool *treestore);
+
+/* full rebuild for already allocated hashtable */
+void BKE_treehash_add_element(void *treehash, struct TreeStoreElem *elem);
+
+/* find first unused element with specific type, nr and id */
+struct TreeStoreElem *BKE_treehash_lookup_unused(void *treehash, short type, short nr, struct ID *id);
+
+/* find user or unused element with specific type, nr and id */
+struct TreeStoreElem *BKE_treehash_lookup_any(void *treehash, short type, short nr, struct ID *id);
+
+/* free treehash structure */
+void BKE_treehash_free(void *treehash);
+
+#endif
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 092c3fcdd42..e9142ef1abd 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -153,6 +153,7 @@ set(SRC
intern/text.c
intern/texture.c
intern/tracking.c
+ intern/treehash.c
intern/unit.c
intern/world.c
intern/writeavi.c
@@ -244,6 +245,7 @@ set(SRC
BKE_text.h
BKE_texture.h
BKE_tracking.h
+ BKE_treehash.h
BKE_unit.h
BKE_utildefines.h
BKE_world.h
diff --git a/source/blender/blenkernel/intern/treehash.c b/source/blender/blenkernel/intern/treehash.c
new file mode 100644
index 00000000000..3d763b22e26
--- /dev/null
+++ b/source/blender/blenkernel/intern/treehash.c
@@ -0,0 +1,133 @@
+#include "BKE_treehash.h"
+
+#include "BLI_ghash.h"
+#include "BLI_mempool.h"
+#include "BLI_utildefines.h"
+
+#include "DNA_outliner_types.h"
+
+#include "MEM_guardedalloc.h"
+
+typedef struct TseGroup
+{
+ TreeStoreElem **elems;
+ int size;
+ int allocated;
+} TseGroup;
+
+/* Allocate structure for TreeStoreElements;
+ * Most of elements in treestore have no duplicates,
+ * so there is no need to preallocate memory for more than one pointer */
+static TseGroup *tse_group_create(void)
+{
+ TseGroup *tse_group = MEM_mallocN(sizeof(TseGroup), "TseGroup");
+ tse_group->elems = MEM_mallocN(sizeof(TreeStoreElem *), "TseGroupElems");
+ tse_group->size = 0;
+ tse_group->allocated = 1;
+ return tse_group;
+}
+
+static void tse_group_add(TseGroup *tse_group, TreeStoreElem *elem)
+{
+ if (tse_group->size == tse_group->allocated) {
+ tse_group->allocated *= 2;
+ tse_group->elems = MEM_reallocN(tse_group->elems, sizeof(TreeStoreElem *) * tse_group->allocated);
+ }
+ tse_group->elems[tse_group->size] = elem;
+ tse_group->size++;
+}
+
+static void tse_group_free(TseGroup *tse_group)
+{
+ MEM_freeN(tse_group->elems);
+ MEM_freeN(tse_group);
+}
+
+static unsigned int tse_hash(const void *ptr)
+{
+ const TreeStoreElem *tse = ptr;
+ unsigned int hash;
+ BLI_assert(tse->type || !tse->nr);
+ hash = BLI_ghashutil_inthash(SET_INT_IN_POINTER((tse->nr << 16) + tse->type));
+ hash ^= BLI_ghashutil_inthash(tse->id);
+ return hash;
+}
+
+static int tse_cmp(const void *a, const void *b)
+{
+ const TreeStoreElem *tse_a = a;
+ const TreeStoreElem *tse_b = b;
+ return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr || tse_a->id != tse_b->id;
+}
+
+static void fill_treehash(void *treehash, BLI_mempool *treestore)
+{
+ TreeStoreElem *tselem;
+ BLI_mempool_iter iter;
+ BLI_mempool_iternew(treestore, &iter);
+ while ((tselem = BLI_mempool_iterstep(&iter))) {
+ BKE_treehash_add_element(treehash, tselem);
+ }
+}
+
+void *BKE_treehash_create_from_treestore(BLI_mempool *treestore)
+{
+ GHash *treehash = BLI_ghash_new(tse_hash, tse_cmp, "treehash");
+ fill_treehash(treehash, treestore);
+ return treehash;
+}
+
+static void free_treehash_group(void *key) {
+ tse_group_free(key);
+}
+
+void *BKE_treehash_rebuild_from_treestore(void *treehash, BLI_mempool *treestore)
+{
+ BLI_ghash_clear(treehash, NULL, free_treehash_group);
+ fill_treehash(treehash, treestore);
+ return treehash;
+}
+
+void BKE_treehash_add_element(void *treehash, TreeStoreElem *elem)
+{
+ TseGroup *group = BLI_ghash_lookup(treehash, elem);
+ if (!group) {
+ group = tse_group_create();
+ BLI_ghash_insert(treehash, elem, group);
+ }
+ tse_group_add(group, elem);
+}
+
+static TseGroup *BKE_treehash_lookup_group(GHash *th, short type, short nr, struct ID *id)
+{
+ TreeStoreElem tse_template;
+ tse_template.type = type;
+ tse_template.nr = type ? nr : 0; // we're picky! :)
+ tse_template.id = id;
+ return BLI_ghash_lookup(th, &tse_template);
+}
+
+TreeStoreElem *BKE_treehash_lookup_unused(void *treehash, short type, short nr, struct ID *id)
+{
+ TseGroup *group = BKE_treehash_lookup_group(treehash, type, nr, id);
+ if (group) {
+ int i;
+ for (i = 0; i < group->size; i++) {
+ if (!group->elems[i]->used) {
+ return group->elems[i];
+ }
+ }
+ }
+ return NULL;
+}
+
+TreeStoreElem *BKE_treehash_lookup_any(void *treehash, short type, short nr, struct ID *id)
+{
+ TseGroup *group = BKE_treehash_lookup_group(treehash, type, nr, id);
+ return group ? group->elems[0] : NULL;
+}
+
+void BKE_treehash_free(void *treehash)
+{
+ BLI_ghash_free(treehash, NULL, free_treehash_group);
+}
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index 8e9558de53a..4688c6e3831 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -33,6 +33,8 @@
* \brief A general (pointer -> pointer) hash table ADT
*/
+#include "BLI_sys_types.h" /* for bool */
+
#ifdef __cplusplus
extern "C" {
#endif
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 554490e2bde..bab015d2a81 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -151,6 +151,7 @@
#include "BKE_text.h" // for txt_extended_ascii_as_utf8
#include "BKE_texture.h"
#include "BKE_tracking.h"
+#include "BKE_treehash.h"
#include "BKE_sound.h"
#include "IMB_imbuf.h" // for proxy / timecode versioning stuff
@@ -5701,12 +5702,8 @@ static void lib_link_screen(FileData *fd, Main *main)
tselem->id = newlibadr(fd, NULL, tselem->id);
}
if (so->treehash) {
- /* update hash table, because it depends on ids too */
- BLI_ghash_clear(so->treehash, NULL, NULL);
- BLI_mempool_iternew(so->treestore, &iter);
- while ((tselem = BLI_mempool_iterstep(&iter))) {
- BLI_ghash_insert(so->treehash, tselem, tselem);
- }
+ /* rebuild hash table, because it depends on ids too */
+ BKE_treehash_rebuild_from_treestore(so->treehash, so->treestore);
}
}
}
@@ -6042,12 +6039,8 @@ void blo_lib_link_screen_restore(Main *newmain, bScreen *curscreen, Scene *cursc
tselem->id = restore_pointer_by_name(newmain, tselem->id, 0);
}
if (so->treehash) {
- /* update hash table, because it depends on ids too */
- BLI_ghash_clear(so->treehash, NULL, NULL);
- BLI_mempool_iternew(so->treestore, &iter);
- while ((tselem = BLI_mempool_iterstep(&iter))) {
- BLI_ghash_insert(so->treehash, tselem, tselem);
- }
+ /* rebuild hash table, because it depends on ids too */
+ BKE_treehash_rebuild_from_treestore(so->treehash, so->treestore);
}
}
}
@@ -6322,7 +6315,7 @@ static bool direct_link_screen(FileData *fd, bScreen *sc)
else if (sl->spacetype == SPACE_OUTLINER) {
SpaceOops *soops = (SpaceOops *) sl;
- /* use newdataadr_no_us and do not free old memory avoidign double
+ /* use newdataadr_no_us and do not free old memory avoiding double
* frees and use of freed memory. this could happen because of a
* bug fixed in revision 58959 where the treestore memory address
* was not unique */
diff --git a/source/blender/editors/space_outliner/outliner_tools.c b/source/blender/editors/space_outliner/outliner_tools.c
index c1950e62817..b346d6b15de 100644
--- a/source/blender/editors/space_outliner/outliner_tools.c
+++ b/source/blender/editors/space_outliner/outliner_tools.c
@@ -57,6 +57,7 @@
#include "BKE_report.h"
#include "BKE_scene.h"
#include "BKE_sequencer.h"
+#include "BKE_treehash.h"
#include "ED_armature.h"
#include "ED_object.h"
@@ -299,17 +300,13 @@ static void object_delete_cb(bContext *C, Scene *scene, TreeElement *te,
if (base == NULL)
base = BKE_scene_base_find(scene, (Object *)tselem->id);
if (base) {
- SpaceOops *soops = CTX_wm_space_outliner(C);
-
// check also library later
if (scene->obedit == base->object)
ED_object_editmode_exit(C, EM_FREEDATA | EM_FREEUNDO | EM_WAITCURSOR | EM_DO_UNDO);
ED_base_object_free_and_unlink(CTX_data_main(C), scene, base);
te->directdata = NULL;
- BLI_ghash_remove(soops->treehash, tselem, NULL, NULL);
tselem->id = NULL;
- BLI_ghash_insert(soops->treehash, tselem, tselem);
}
}
diff --git a/source/blender/editors/space_outliner/outliner_tree.c b/source/blender/editors/space_outliner/outliner_tree.c
index 2a6320b83b1..0a9478ed52c 100644
--- a/source/blender/editors/space_outliner/outliner_tree.c
+++ b/source/blender/editors/space_outliner/outliner_tree.c
@@ -74,6 +74,7 @@
#include "BKE_modifier.h"
#include "BKE_sequencer.h"
#include "BKE_idcode.h"
+#include "BKE_treehash.h"
#include "ED_armature.h"
#include "ED_screen.h"
@@ -116,9 +117,8 @@ static void outliner_storage_cleanup(SpaceOops *soops)
if (BLI_mempool_count(ts) == unused) {
BLI_mempool_destroy(ts);
soops->treestore = NULL;
-
if (soops->treehash) {
- BLI_ghash_free(soops->treehash, NULL, NULL);
+ BKE_treehash_free(soops->treehash);
soops->treehash = NULL;
}
}
@@ -135,14 +135,9 @@ static void outliner_storage_cleanup(SpaceOops *soops)
}
BLI_mempool_destroy(ts);
soops->treestore = new_ts;
-
if (soops->treehash) {
/* update hash table to fix broken pointers */
- BLI_ghash_clear(soops->treehash, NULL, NULL);
- BLI_mempool_iternew(soops->treestore, &iter);
- while ((tselem = BLI_mempool_iterstep(&iter))) {
- BLI_ghash_insert(soops->treehash, tselem, tselem);
- }
+ BKE_treehash_rebuild_from_treestore(soops->treehash, soops->treestore);
}
}
}
@@ -150,67 +145,22 @@ static void outliner_storage_cleanup(SpaceOops *soops)
}
}
-/* This function hashes only by type, nr and id, while cmp function also compares 'used' flag;
- * This is done to skip full treehash rebuild in outliner_storage_cleanup;
- * In general hashing by type, nr and id should be enough to distribute elements in buckets uniformly */
-static unsigned int tse_hash(const void *ptr)
-{
- const TreeStoreElem *tse = (const TreeStoreElem *)ptr;
- unsigned int hash;
- BLI_assert(tse->type || !tse->nr);
- hash = BLI_ghashutil_inthash(SET_INT_IN_POINTER((tse->nr << 16) + tse->type));
- hash ^= BLI_ghashutil_inthash(tse->id);
- return hash;
-}
-
-static int tse_cmp(const void *a, const void *b)
-{
- const TreeStoreElem *tse_a = (const TreeStoreElem *)a;
- const TreeStoreElem *tse_b = (const TreeStoreElem *)b;
- return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr ||
- tse_a->id != tse_b->id || tse_a->used != tse_b->used;
-}
-
-static TreeStoreElem *lookup_treehash(GHash *th, short type, short nr, short used, ID *id)
-{
- TreeStoreElem tse_template;
- tse_template.type = type;
- tse_template.nr = type ? nr : 0; // we're picky! :)
- tse_template.id = id;
- tse_template.used = used;
- return BLI_ghash_lookup(th, &tse_template);
-}
-
static void check_persistent(SpaceOops *soops, TreeElement *te, ID *id, short type, short nr)
{
- /* When treestore comes directly from readfile.c, treehash is empty;
- * In this case we don't want to get TSE_CLOSED while adding elements one by one,
- * that is why this function restores treehash */
- bool restore_treehash = (soops->treestore && !soops->treehash);
TreeStoreElem *tselem;
if (soops->treestore == NULL) {
/* if treestore was not created in readfile.c, create it here */
soops->treestore = BLI_mempool_create(sizeof(TreeStoreElem), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
- }
- if (soops->treehash == NULL) {
- soops->treehash = BLI_ghash_new(tse_hash, tse_cmp, "treehash");
- /* treehash elements are not required to be unique; see soops->treehash comment */
- BLI_ghash_flag_set(soops->treehash, GHASH_FLAG_ALLOW_DUPES);
}
-
- if (restore_treehash) {
- BLI_mempool_iter iter;
- BLI_mempool_iternew(soops->treestore, &iter);
- while ((tselem = BLI_mempool_iterstep(&iter))) {
- BLI_ghash_insert(soops->treehash, tselem, tselem);
- }
+ if (soops->treehash == NULL) {
+ soops->treehash = BKE_treehash_create_from_treestore(soops->treestore);
}
/* find any unused tree element in treestore and mark it as used
* (note that there may be multiple unused elements in case of linked objects) */
- tselem = lookup_treehash(soops->treehash, type, nr, 0, id);
+ tselem = BKE_treehash_lookup_unused(soops->treehash, type, nr, id);
if (tselem) {
te->store_elem = tselem;
tselem->used = 1;
@@ -225,7 +175,7 @@ static void check_persistent(SpaceOops *soops, TreeElement *te, ID *id, short ty
tselem->used = 0;
tselem->flag = TSE_CLOSED;
te->store_elem = tselem;
- BLI_ghash_insert(soops->treehash, tselem, tselem);
+ BKE_treehash_add_element(soops->treehash, tselem);
}
/* ********************************************************* */
@@ -270,7 +220,7 @@ TreeElement *outliner_find_tse(SpaceOops *soops, TreeStoreElem *tse)
if (tse->id == NULL) return NULL;
/* check if 'tse' is in treestore */
- tselem = lookup_treehash(soops->treehash, tse->type, tse->nr, tse->used, tse->id);
+ tselem = BKE_treehash_lookup_any(soops->treehash, tse->type, tse->nr, tse->id);
if (tselem)
return outliner_find_tree_element(&soops->tree, tselem);
diff --git a/source/blender/editors/space_outliner/space_outliner.c b/source/blender/editors/space_outliner/space_outliner.c
index 874852ee320..d695ffa46d5 100644
--- a/source/blender/editors/space_outliner/space_outliner.c
+++ b/source/blender/editors/space_outliner/space_outliner.c
@@ -43,6 +43,7 @@
#include "BKE_context.h"
#include "BKE_screen.h"
#include "BKE_scene.h"
+#include "BKE_treehash.h"
#include "ED_space_api.h"
#include "ED_screen.h"
@@ -435,7 +436,7 @@ static void outliner_free(SpaceLink *sl)
BLI_mempool_destroy(soutliner->treestore);
}
if (soutliner->treehash) {
- BLI_ghash_free(soutliner->treehash, NULL, NULL);
+ BKE_treehash_free(soutliner->treehash);
}
}
diff --git a/source/blender/makesdna/DNA_space_types.h b/source/blender/makesdna/DNA_space_types.h
index 5c308083f3c..e8e5a01ca84 100644
--- a/source/blender/makesdna/DNA_space_types.h
+++ b/source/blender/makesdna/DNA_space_types.h
@@ -262,11 +262,8 @@ typedef struct SpaceOops {
short flag, outlinevis, storeflag, search_flags;
- /* search index for every element in treestore;
- * It is ok for treehash to contain duplicates, because the semantics of its usage
- * allows duplicates (see check_persistent)
- */
- struct GHash *treehash;
+ /* pointers to treestore elements, grouped by (id, type, nr) in hashtable for faster searching */
+ void *treehash;
} SpaceOops;
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-31 19:07:22 +0300