Fix state losses for recursive outliner trees (e.g. datablocks editor)

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".

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;