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

3 files changed, 11 insertions, 63 deletions

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);
 	}
 }