Fix state losses for recursive outliner trees (e.g. datablocks editor)
authorSv. Lockal <lockalsash@gmail.com>
Fri, 23 Aug 2013 20:35:00 +0000 (20:35 +0000)
committerSv. Lockal <lockalsash@gmail.com>
Fri, 23 Aug 2013 20:35:00 +0000 (20:35 +0000)
In previous optimization in outliner I assumed that order in treehash was not important.
But testing outliner in datablocks mode revealed a problem: when user expands multiple recursive levels and then closes any element, it always closed the top level of recursion.
Now it should work fine with recursive trees.
Now treehash contains groups of elements indexed by (id,nr,type). Adding an element with the same (id,nr,type) results in appending it to existing group. No duplicates are possible in treehash.
This commit should also make lookups a little bit faster, because searching in small arrays by "used" is faster than searching in hashtable with duplicates by "id,nr,type,used".

source/blender/blenkernel/BKE_treehash.h [new file with mode: 0644]
source/blender/blenkernel/CMakeLists.txt
source/blender/blenkernel/intern/treehash.c [new file with mode: 0644]
source/blender/blenlib/BLI_ghash.h
source/blender/blenloader/intern/readfile.c
source/blender/editors/space_outliner/outliner_tools.c
source/blender/editors/space_outliner/outliner_tree.c
source/blender/editors/space_outliner/space_outliner.c
source/blender/makesdna/DNA_space_types.h

diff --git a/source/blender/blenkernel/BKE_treehash.h b/source/blender/blenkernel/BKE_treehash.h
new file mode 100644 (file)
index 0000000..54deef1
--- /dev/null
@@ -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
index 092c3fcdd420f67a00742285c15ac93622596c43..e9142ef1abdaada2b2b3b264c42ad696013fad77 100644 (file)
@@ -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 (file)
index 0000000..3d763b2
--- /dev/null
@@ -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);
+}
index 8e9558de53af01b1f5da27c1645b0134df0665a7..4688c6e3831741aa0cdd861947f0f5f131aef4fc 100644 (file)
@@ -33,6 +33,8 @@
  *  \brief A general (pointer -> pointer) hash table ADT
  */
 
+#include "BLI_sys_types.h" /* for bool */
+
 #ifdef __cplusplus
 extern "C" {
 #endif
index 554490e2bde2c3b124a0e6df988b4822eaeaa06a..bab015d2a81c3945c6b129d4777630bf132a8788 100644 (file)
 #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 */
index c1950e62817f345be420ce3fcf483750fe29484c..b346d6b15deca1393d9995b003d74394530f64f6 100644 (file)
@@ -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);
        }
 }
 
index 2a6320b83b11b8f827afb25f48959e509c6bbc6f..0a9478ed52c9446706acfaaee6d0dcb3cf3b1618 100644 (file)
@@ -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);
        
index 874852ee320749b4e5e66c963c5e6381b0a11761..d695ffa46d58573f89a30c74bd3ad6d72f9d60e6 100644 (file)
@@ -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);
        }
 }
 
index 5c308083f3cadc16412cf5b5225c4007633a1992..e8e5a01ca84ee5996ded3638667eb3241ab307b4 100644 (file)
@@ -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;