[Bf-blender-cvs] [3598ef2] object_nodes: Use a global node index assignment to enable sorted sets for nodes.
Lukas Tönne
noreply at git.blender.org
Tue Jan 12 12:38:25 CET 2016
Commit: 3598ef253694449248f60a998d78b54428a8c477
Author: Lukas Tönne
Date: Thu Jan 7 12:11:15 2016 +0100
Branches: object_nodes
https://developer.blender.org/rB3598ef253694449248f60a998d78b54428a8c477
Use a global node index assignment to enable sorted sets for nodes.
This simplifies code generation because we can use a set with efficient
lookup which also keeps a valid ordering of nodes as dictated by links.
Since any generated code uses only subsets of nodes, the ordering still
is valid for any BasicBlock.
===================================================================
M source/blender/blenvm/compile/bvm_codegen.cc
M source/blender/blenvm/compile/bvm_codegen.h
M source/blender/blenvm/compile/bvm_nodegraph.cc
M source/blender/blenvm/compile/bvm_nodegraph.h
===================================================================
diff --git a/source/blender/blenvm/compile/bvm_codegen.cc b/source/blender/blenvm/compile/bvm_codegen.cc
index 7872485..43508f7 100644
--- a/source/blender/blenvm/compile/bvm_codegen.cc
+++ b/source/blender/blenvm/compile/bvm_codegen.cc
@@ -83,7 +83,7 @@ StackIndex Compiler::assign_stack_index(const TypeDesc &typedesc)
void Compiler::resolve_basic_block_symbols(const NodeGraph &graph, BasicBlock &block)
{
- for (NodeList::const_iterator it = block.nodes.begin(); it != block.nodes.end(); ++it) {
+ for (OrderedNodeSet::const_iterator it = block.nodes.begin(); it != block.nodes.end(); ++it) {
const NodeInstance &node = **it;
/* local arguments for expression inputs */
@@ -149,8 +149,8 @@ void Compiler::resolve_basic_block_symbols(const NodeGraph &graph, BasicBlock &b
}
void Compiler::expression_node_append(const NodeInstance *node,
- NodeList &sorted_nodes,
- NodeSet &visited)
+ OrderedNodeSet &nodes,
+ OrderedNodeSet &visited)
{
if (node->type->is_kernel_node())
return;
@@ -162,16 +162,16 @@ void Compiler::expression_node_append(const NodeInstance *node,
for (size_t i = 0; i < node->num_inputs(); ++i) {
ConstOutputKey link = node->link(i);
if (link) {
- expression_node_append(link.node, sorted_nodes, visited);
+ expression_node_append(link.node, nodes, visited);
}
}
- sorted_nodes.push_back(node);
+ nodes.insert(node);
}
void Compiler::graph_node_append(const NodeInstance *node,
- NodeList &sorted_nodes,
- NodeSet &visited)
+ OrderedNodeSet &nodes,
+ OrderedNodeSet &visited)
{
if (visited.find(node) != visited.end())
return;
@@ -185,23 +185,23 @@ void Compiler::graph_node_append(const NodeInstance *node,
BasicBlock &expr_block = expression_map[node->input(i)];
if (link) {
- NodeSet expr_visited;
+ OrderedNodeSet expr_visited;
expression_node_append(link.node, expr_block.nodes, expr_visited);
}
}
else {
if (link) {
- graph_node_append(link.node, sorted_nodes, visited);
+ graph_node_append(link.node, nodes, visited);
}
}
}
- sorted_nodes.push_back(node);
+ nodes.insert(node);
}
void Compiler::sort_graph_nodes(const NodeGraph &graph)
{
- NodeSet visited;
+ OrderedNodeSet visited;
for (NodeGraph::NodeInstanceMap::const_iterator it = graph.nodes.begin(); it != graph.nodes.end(); ++it) {
graph_node_append(it->second, main.nodes, visited);
@@ -441,7 +441,7 @@ int Compiler::codegen_basic_block(const BasicBlock &block,
{
int entry_point = current_address();
- for (NodeList::const_iterator it = block.nodes.begin(); it != block.nodes.end(); ++it) {
+ for (OrderedNodeSet::const_iterator it = block.nodes.begin(); it != block.nodes.end(); ++it) {
const NodeInstance &node = **it;
/* store values for unconnected inputs */
diff --git a/source/blender/blenvm/compile/bvm_codegen.h b/source/blender/blenvm/compile/bvm_codegen.h
index cd3106a..f38489d 100644
--- a/source/blender/blenvm/compile/bvm_codegen.h
+++ b/source/blender/blenvm/compile/bvm_codegen.h
@@ -49,15 +49,21 @@ struct NodeGraph;
struct NodeInstance;
struct TypeDesc;
-typedef std::vector<const NodeInstance *> NodeList;
-typedef std::set<const NodeInstance *> NodeSet;
+struct NodeIndexCmp {
+ bool operator () (const NodeInstance *a, const NodeInstance *b) const
+ {
+ return a->index < b->index;
+ }
+};
+
+typedef std::set<const NodeInstance *, NodeIndexCmp> OrderedNodeSet;
typedef std::map<ConstInputKey, StackIndex> InputIndexMap;
typedef std::map<ConstOutputKey, StackIndex> OutputIndexMap;
typedef std::map<ConstOutputKey, int> SocketUserMap;
struct BasicBlock {
BasicBlock() : entry_point(0), return_index(BVM_STACK_INVALID) {}
- NodeList nodes;
+ OrderedNodeSet nodes;
InputIndexMap input_index;
OutputIndexMap output_index;
int entry_point;
@@ -98,8 +104,8 @@ protected:
const SocketUserMap &socket_users) const;
int codegen_main(const NodeGraph &graph);
- void expression_node_append(const NodeInstance *node, NodeList &sorted_nodes, NodeSet &visited);
- void graph_node_append(const NodeInstance *node, NodeList &sorted_nodes, NodeSet &visited);
+ void expression_node_append(const NodeInstance *node, OrderedNodeSet &sorted_nodes, OrderedNodeSet &visited);
+ void graph_node_append(const NodeInstance *node, OrderedNodeSet &sorted_nodes, OrderedNodeSet &visited);
void sort_graph_nodes(const NodeGraph &graph);
const BasicBlock &main_block() const { return main; }
diff --git a/source/blender/blenvm/compile/bvm_nodegraph.cc b/source/blender/blenvm/compile/bvm_nodegraph.cc
index c3f2846..5df6e8e 100644
--- a/source/blender/blenvm/compile/bvm_nodegraph.cc
+++ b/source/blender/blenvm/compile/bvm_nodegraph.cc
@@ -412,7 +412,7 @@ bool InputKey::is_expression() const
/* ------------------------------------------------------------------------- */
NodeInstance::NodeInstance(const NodeType *type, const string &name) :
- type(type), name(name)
+ type(type), name(name), index(0)
{
}
@@ -853,10 +853,35 @@ void NodeGraph::remove_unused_nodes()
}
}
+static void assign_node_index(NodeInstance *node, int *next_index)
+{
+ if (node->index > 0)
+ return;
+
+ for (int i = 0; i < node->num_inputs(); ++i) {
+ NodeInstance *link_node = node->link(i).node;
+ if (link_node) {
+ assign_node_index(link_node, next_index);
+ }
+ }
+
+ node->index = (*next_index)++;
+}
+
+/* assign a global index to each node to allow sorted sets */
+void NodeGraph::sort_nodes()
+{
+ int next_index = 1;
+ for (NodeInstanceMap::iterator it = nodes.begin(); it != nodes.end(); ++it) {
+ assign_node_index(it->second, &next_index);
+ }
+}
+
void NodeGraph::finalize()
{
skip_pass_nodes();
remove_unused_nodes();
+ sort_nodes();
}
/* ------------------------------------------------------------------------- */
diff --git a/source/blender/blenvm/compile/bvm_nodegraph.h b/source/blender/blenvm/compile/bvm_nodegraph.h
index 0b33c3c..a605daa 100644
--- a/source/blender/blenvm/compile/bvm_nodegraph.h
+++ b/source/blender/blenvm/compile/bvm_nodegraph.h
@@ -244,6 +244,7 @@ struct NodeInstance {
const NodeType *type;
string name;
InputMap inputs;
+ int index; /* ordering index */
MEM_CXX_CLASS_ALLOC_FUNCS("BVM:NodeInstance")
};
@@ -314,6 +315,7 @@ protected:
OutputKey find_root(const OutputKey &key);
void skip_pass_nodes();
void remove_unused_nodes();
+ void sort_nodes();
public:
NodeInstanceMap nodes;
More information about the Bf-blender-cvs
mailing list