diff options
-rw-r--r-- | source/blender/blenkernel/BKE_treehash.h | 52 | ||||
-rw-r--r-- | source/blender/blenkernel/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/treehash.c | 133 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_ghash.h | 2 | ||||
-rw-r--r-- | source/blender/blenloader/intern/readfile.c | 19 | ||||
-rw-r--r-- | source/blender/editors/space_outliner/outliner_tools.c | 5 | ||||
-rw-r--r-- | source/blender/editors/space_outliner/outliner_tree.c | 66 | ||||
-rw-r--r-- | source/blender/editors/space_outliner/space_outliner.c | 3 | ||||
-rw-r--r-- | source/blender/makesdna/DNA_space_types.h | 7 |
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; |