[Bf-blender-cvs] [10f076da2d6] blender2.8: Depsgraph: Introduce flat list of ID nodes

[Sergey Sharybin]

Commit: 10f076da2d687a77a317e060bf69d95fb49ad075
Author: Sergey Sharybin
Date:   Wed Nov 8 14:29:58 2017 +0100
Branches: blender2.8
https://developer.blender.org/rB10f076da2d687a77a317e060bf69d95fb49ad075

Depsgraph: Introduce flat list of ID nodes

The idea is to allow iterating over ID nodes in exact order of their
construction, and in order which will not change dependent on memory
pointers or anything.

===================================================================

M	source/blender/depsgraph/intern/depsgraph.cc
M	source/blender/depsgraph/intern/depsgraph.h

===================================================================

diff --git a/source/blender/depsgraph/intern/depsgraph.cc b/source/blender/depsgraph/intern/depsgraph.cc
index 03e5f2235bb..05e66318d86 100644
--- a/source/blender/depsgraph/intern/depsgraph.cc
+++ b/source/blender/depsgraph/intern/depsgraph.cc
@@ -301,6 +301,7 @@ IDDepsNode *Depsgraph::add_id_node(ID *id, bool do_tag, ID *id_cow_hint)
 		 * referencing to.
 		 */
 		BLI_ghash_insert(id_hash, id, id_node);
+		id_nodes.push_back(id_node);
 	}
 	else if (do_tag) {
 		id->tag |= LIB_TAG_DOIT;
@@ -310,6 +311,7 @@ IDDepsNode *Depsgraph::add_id_node(ID *id, bool do_tag, ID *id_cow_hint)
 
 void Depsgraph::clear_id_nodes()
 {
+	/* Free memory used by ID nodes. */
 	if (use_copy_on_write) {
 		/* Stupid workaround to ensure we free IDs in a proper order. */
 		GHASH_FOREACH_BEGIN(IDDepsNode *, id_node, id_hash)
@@ -335,6 +337,9 @@ void Depsgraph::clear_id_nodes()
 		OBJECT_GUARDED_DELETE(id_node, IDDepsNode);
 	}
 	GHASH_FOREACH_END();
+	/* Clear containers. */
+	BLI_ghash_clear(id_hash, NULL, NULL);
+	id_nodes.clear();
 }
 
 /* Add new relationship between two nodes. */
@@ -441,7 +446,6 @@ void Depsgraph::add_entry_tag(OperationDepsNode *node)
 void Depsgraph::clear_all_nodes()
 {
 	clear_id_nodes();
-	BLI_ghash_clear(id_hash, NULL, NULL);
 	if (time_source != NULL) {
 		OBJECT_GUARDED_DELETE(time_source, TimeSourceDepsNode);
 		time_source = NULL;
diff --git a/source/blender/depsgraph/intern/depsgraph.h b/source/blender/depsgraph/intern/depsgraph.h
index 889eb33c1bf..1b4dca569d7 100644
--- a/source/blender/depsgraph/intern/depsgraph.h
+++ b/source/blender/depsgraph/intern/depsgraph.h
@@ -93,7 +93,9 @@ struct DepsRelation {
 
 /* Dependency Graph object */
 struct Depsgraph {
+	// TODO(sergey): Go away from C++ container and use some native BLI.
 	typedef vector<OperationDepsNode *> OperationNodes;
+	typedef vector<IDDepsNode *> IDDepsNodes;
 
 	Depsgraph();
 	~Depsgraph();
@@ -139,10 +141,17 @@ struct Depsgraph {
 
 	/* Core Graph Functionality ........... */
 
-	/* <ID : IDDepsNode> mapping from ID blocks to nodes representing these blocks
-	 * (for quick lookups). */
+	/* <ID : IDDepsNode> mapping from ID blocks to nodes representing these
+	 * blocks, used for quick lookups.
+	 */
 	GHash *id_hash;
 
+	/* Ordered list of ID nodes, order matches ID allocation order.
+	 * Used for faster iteration, especially for areas which are critical to
+	 * keep exact order of iteration.
+	 */
+	IDDepsNodes id_nodes;
+
 	/* Top-level time source node. */
 	TimeSourceDepsNode *time_source;