source/blender/depsgraph/intern/depsgraph_query_foreach.cc

   1 /*
   2  * ***** BEGIN GPL LICENSE BLOCK *****
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  * The Original Code is Copyright (C) 2017 Blender Foundation.
  19  * All rights reserved.
  20  *
  21  * Original Author: Sergey Sharybin
  22  * Contributor(s): None Yet
  23  *
  24  * ***** END GPL LICENSE BLOCK *****
  25  */
  26
  27 /** \file blender/depsgraph/intern/depsgraph_query_foreach.cc
  28  *  \ingroup depsgraph
  29  *
  30  * Implementation of Querying and Filtering API's
  31  */
  32
  33 // TODO(sergey): Use some sort of wrapper.
  34 #include <deque>
  35
  36 #include "MEM_guardedalloc.h"
  37
  38 extern "C" {
  39 #include "BLI_utildefines.h"
  40 #include "BLI_ghash.h"
  41 } /* extern "C" */
  42
  43 #include "DNA_object_types.h"
  44 #include "DNA_scene_types.h"
  45
  46 #include "DEG_depsgraph.h"
  47 #include "DEG_depsgraph_query.h"
  48
  49 #include "intern/depsgraph_intern.h"
  50
  51 #include "intern/nodes/deg_node.h"
  52 #include "intern/nodes/deg_node_component.h"
  53 #include "intern/nodes/deg_node_id.h"
  54 #include "intern/nodes/deg_node_operation.h"
  55
  56 #include "util/deg_util_foreach.h"
  57
  58 /* ************************ DEG TRAVERSAL ********************* */
  59
  60 namespace DEG {
  61
  62 typedef std::deque<OperationDepsNode *> TraversalQueue;
  63
  64 static void deg_foreach_clear_flags(const Depsgraph *graph)
  65 {
  66         foreach (OperationDepsNode *op_node, graph->operations) {
  67                 op_node->scheduled = false;
  68         }
  69         foreach (IDDepsNode *id_node, graph->id_nodes) {
  70                 id_node->done = false;
  71         }
  72 }
  73
  74 static void deg_foreach_dependent_ID(const Depsgraph *graph,
  75                                      const ID *id,
  76                                      DEGForeachIDCallback callback,
  77                                      void *user_data)
  78 {
  79         /* Start with getting ID node from the graph. */
  80         IDDepsNode *id_node = graph->find_id_node(id);
  81         if (id_node == NULL) {
  82                 /* TODO(sergey): Shall we inform or assert here about attempt to start
  83                  * iterating over non-existing ID?
  84                  */
  85                 return;
  86         }
  87         /* Make sure all runtime flags are ready and clear. */
  88         deg_foreach_clear_flags(graph);
  89         /* Start with scheduling all operations from ID node. */
  90         TraversalQueue queue;
  91         GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components)
  92         {
  93                 foreach (OperationDepsNode *op_node, comp_node->operations) {
  94                         queue.push_back(op_node);
  95                         op_node->scheduled = true;
  96                 }
  97         }
  98         GHASH_FOREACH_END();
  99         id_node->done = true;
 100         /* Process the queue. */
 101         while (!queue.empty()) {
 102                 /* get next operation node to process. */
 103                 OperationDepsNode *op_node = queue.front();
 104                 queue.pop_front();
 105                 for (;;) {
 106                         /* Check whether we need to inform callee about corresponding ID node. */
 107                         ComponentDepsNode *comp_node = op_node->owner;
 108                         IDDepsNode *id_node = comp_node->owner;
 109                         if (!id_node->done) {
 110                                 /* TODO(sergey): Is it orig or CoW? */
 111                                 callback(id_node->id_orig, user_data);
 112                                 id_node->done = true;
 113                         }
 114                         /* Schedule outgoing operation nodes. */
 115                         if (op_node->outlinks.size() == 1) {
 116                                 OperationDepsNode *to_node = (OperationDepsNode *)op_node->outlinks[0]->to;
 117                                 if (to_node->scheduled == false) {
 118                                         to_node->scheduled = true;
 119                                         op_node = to_node;
 120                                 }
 121                                 else {
 122                                         break;
 123                                 }
 124                         }
 125                         else {
 126                                 foreach (DepsRelation *rel, op_node->outlinks) {
 127                                         OperationDepsNode *to_node = (OperationDepsNode *)rel->to;
 128                                         if (to_node->scheduled == false) {
 129                                                 queue.push_front(to_node);
 130                                                 to_node->scheduled = true;
 131                                         }
 132                                 }
 133                                 break;
 134                         }
 135                 }
 136         }
 137 }
 138
 139 }  // namespace DEG
 140
 141 void DEG_foreach_dependent_ID(const Depsgraph *depsgraph,
 142                               const ID *id,
 143                               DEGForeachIDCallback callback, void *user_data)
 144 {
 145         DEG::deg_foreach_dependent_ID((const DEG::Depsgraph *)depsgraph,
 146                                       id,
 147                                       callback, user_data);
 148 }