Depsgraph: use BLI::Vector for Relations

Reviewers: sergey

Differential Revision: https://developer.blender.org/D7556

source/blender/depsgraph/intern/builder/deg_builder_relations.cc

@@ -2737,7 +2737,7 @@ void DepsgraphRelationBuilder::build_copy_on_write_relations(IDNode *id_node)
       if (op_node == op_entry) {
         continue;
       }
-      if (op_node->inlinks.size() == 0) {
+      if (op_node->inlinks.is_empty()) {
         Relation *rel = graph_->add_new_relation(op_cow, op_node, "CoW Dependency");
         rel->flag |= rel_flag;
       }

source/blender/depsgraph/intern/builder/deg_builder_remove_noop.cc

@@ -43,7 +43,7 @@ static inline bool is_unused_noop(OperationNode *op_node)
   if (op_node->flag & OperationFlag::DEPSOP_FLAG_PINNED) {
     return false;
   }
-  return op_node->is_noop() && op_node->outlinks.empty();
+  return op_node->is_noop() && op_node->outlinks.is_empty();
 }
 
 void deg_graph_remove_unused_noops(Depsgraph *graph)
@@ -61,7 +61,7 @@ void deg_graph_remove_unused_noops(Depsgraph *graph)
     OperationNode *to_remove = queue.front();
     queue.pop_front();
 
-    while (!to_remove->inlinks.empty()) {
+    while (!to_remove->inlinks.is_empty()) {
       Relation *rel_in = to_remove->inlinks[0];
       Node *dependency = rel_in->from;
 

source/blender/depsgraph/intern/builder/deg_builder_transitive.cc

@@ -72,6 +72,8 @@ static void deg_graph_tag_paths_recursive(Node *node)
 void deg_graph_transitive_reduction(Depsgraph *graph)
 {
   int num_removed_relations = 0;
+  Vector<Relation *> relations_to_remove;
+
   for (OperationNode *target : graph->operations) {
     /* Clear tags. */
     for (OperationNode *node : graph->operations) {
@@ -85,25 +87,24 @@ void deg_graph_transitive_reduction(Depsgraph *graph)
       deg_graph_tag_paths_recursive(rel->from);
     }
     /* Remove redundant paths to the target. */
-    for (Node::Relations::const_iterator it_rel = target->inlinks.begin();
-         it_rel != target->inlinks.end();) {
-      Relation *rel = *it_rel;
+    for (Relation *rel : target->inlinks) {
       if (rel->from->type == NodeType::TIMESOURCE) {
         /* HACK: time source nodes don't get "custom_flags" flag
          * set/cleared. */
         /* TODO: there will be other types in future, so iterators above
          * need modifying. */
-        ++it_rel;
+        continue;
       }
       else if (rel->from->custom_flags & OP_REACHABLE) {
-        rel->unlink();
-        OBJECT_GUARDED_DELETE(rel, Relation);
-        num_removed_relations++;
-      }
-      else {
-        ++it_rel;
+        relations_to_remove.append(rel);
       }
     }
+    for (Relation *rel : relations_to_remove) {
+      rel->unlink();
+      OBJECT_GUARDED_DELETE(rel, Relation);
+    }
+    num_removed_relations += relations_to_remove.size();
+    relations_to_remove.clear();
   }
   DEG_DEBUG_PRINTF((::Depsgraph *)graph, BUILD, "Removed %d relations\n", num_removed_relations);
 }

source/blender/depsgraph/intern/depsgraph.cc

@@ -60,12 +60,6 @@ extern "C" {
 
 namespace DEG {
 
-/* TODO(sergey): Find a better place for this. */
-template<typename T> static void remove_from_vector(vector<T> *vector, const T &value)
-{
-  vector->erase(std::remove(vector->begin(), vector->end(), value), vector->end());
-}
-
 Depsgraph::Depsgraph(Main *bmain, Scene *scene, ViewLayer *view_layer, eEvaluationMode mode)
     : time_source(nullptr),
       need_update(true),

source/blender/depsgraph/intern/depsgraph_relation.cc

@@ -30,12 +30,6 @@
 
 namespace DEG {
 
-/* TODO(sergey): Find a better place for this. */
-template<typename T> static void remove_from_vector(vector<T> *vector, const T &value)
-{
-  vector->erase(std::remove(vector->begin(), vector->end(), value), vector->end());
-}
-
 Relation::Relation(Node *from, Node *to, const char *description)
     : from(from), to(to), name(description), flag(0)
 {
@@ -52,8 +46,8 @@ Relation::Relation(Node *from, Node *to, const char *description)
    *
    * - Un-registering relation is not a cheap operation, so better to have it
    *   as an explicit call if we need this. */
-  from->outlinks.push_back(this);
-  to->inlinks.push_back(this);
+  from->outlinks.append(this);
+  to->inlinks.append(this);
 }
 
 Relation::~Relation()
@@ -66,8 +60,8 @@ void Relation::unlink()
 {
   /* Sanity check. */
   BLI_assert(from != nullptr && to != nullptr);
-  remove_from_vector(&from->outlinks, this);
-  remove_from_vector(&to->inlinks, this);
+  from->outlinks.remove_first_occurrence_and_reorder(this);
+  to->inlinks.remove_first_occurrence_and_reorder(this);
 }
 
 }  // namespace DEG

source/blender/depsgraph/intern/node/deg_node.h

@@ -163,7 +163,7 @@ struct Node {
    * The reason why all depsgraph nodes are descended from this type (apart
    * from basic serialization benefits - from the typeinfo) is that we can
    * have relationships between these nodes. */
-  typedef vector<Relation *> Relations;
+  typedef Vector<Relation *> Relations;
 
   string name;        /* Identifier - mainly for debugging purposes. */
   NodeType type;      /* Structural type of node. */