[Bf-blender-cvs] [984edb2c4e6] master: Nodes: Replace implementation of select next/prev type operator

[Hans Goudey]

Commit: 984edb2c4e6a8196dace0a26c43df9af97157b5d
Author: Hans Goudey
Date:   Sun Nov 20 13:55:36 2022 -0600
Branches: master
https://developer.blender.org/rB984edb2c4e6a8196dace0a26c43df9af97157b5d

Nodes: Replace implementation of select next/prev type operator

The previous code was quadratic; it looped over every link for every
node. For one large node tree I tested the operator took 20ms. On the
same node tree it now takes less than 1ms.

The change replaces the current building of the "dependency list"
on every call with a use of the topology cache from 25e307d725d0b924fb.

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

M	source/blender/editors/space_node/node_select.cc

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

diff --git a/source/blender/editors/space_node/node_select.cc b/source/blender/editors/space_node/node_select.cc
index d69b4b9c6c3..2604c6fa1dc 100644
--- a/source/blender/editors/space_node/node_select.cc
+++ b/source/blender/editors/space_node/node_select.cc
@@ -1235,65 +1235,52 @@ void NODE_OT_select_linked_from(wmOperatorType *ot)
 /** \name Select Same Type Step Operator
  * \{ */
 
+static bool nodes_are_same_type_for_select(const bNode &a, const bNode &b)
+{
+  return a.type == b.type;
+}
+
 static int node_select_same_type_step_exec(bContext *C, wmOperator *op)
 {
   SpaceNode *snode = CTX_wm_space_node(C);
   ARegion *region = CTX_wm_region(C);
-  bNode **node_array;
-  bNode *active = nodeGetActive(snode->edittree);
-  int totnodes;
-  const bool revert = RNA_boolean_get(op->ptr, "prev");
-
-  ntreeGetDependencyList(snode->edittree, &node_array, &totnodes);
-
-  if (totnodes > 1) {
-    int a;
-
-    for (a = 0; a < totnodes; a++) {
-      if (node_array[a] == active) {
-        break;
-      }
-    }
+  const bool prev = RNA_boolean_get(op->ptr, "prev");
+  bNode &active_node = *nodeGetActive(snode->edittree);
 
-    bNode *node = nullptr;
-
-    while (node == nullptr) {
-      if (revert) {
-        a--;
-      }
-      else {
-        a++;
-      }
-
-      if (a < 0 || a >= totnodes) {
-        break;
-      }
+  bNodeTree &node_tree = *snode->edittree;
+  node_tree.ensure_topology_cache();
+  if (node_tree.all_nodes().size() == 1) {
+    return OPERATOR_CANCELLED;
+  }
 
-      node = node_array[a];
+  const Span<const bNode *> toposort = node_tree.toposort_left_to_right();
+  const int index = toposort.first_index(&active_node);
 
-      if (node->type == active->type) {
-        break;
-      }
-      node = nullptr;
+  int new_index = index;
+  while (true) {
+    new_index += (prev ? -1 : 1);
+    if (!toposort.index_range().contains(new_index)) {
+      return OPERATOR_CANCELLED;
     }
-    if (node) {
-      active = node;
+    if (nodes_are_same_type_for_select(*toposort[new_index], active_node)) {
+      break;
     }
+  }
 
-    node_select_single(*C, *active);
-
-    /* is note outside view? */
-    if (active->runtime->totr.xmax < region->v2d.cur.xmin ||
-        active->runtime->totr.xmin > region->v2d.cur.xmax ||
-        active->runtime->totr.ymax < region->v2d.cur.ymin ||
-        active->runtime->totr.ymin > region->v2d.cur.ymax) {
-      const int smooth_viewtx = WM_operator_smooth_viewtx_get(op);
-      space_node_view_flag(*C, *snode, *region, NODE_SELECT, smooth_viewtx);
-    }
+  bNode *new_active_node = node_tree.all_nodes()[toposort[new_index]->runtime->index_in_tree];
+  if (new_active_node == &active_node) {
+    return OPERATOR_CANCELLED;
   }
 
-  if (node_array) {
-    MEM_freeN(node_array);
+  node_select_single(*C, *new_active_node);
+
+  /* is note outside view? */
+  if (new_active_node->runtime->totr.xmax < region->v2d.cur.xmin ||
+      new_active_node->runtime->totr.xmin > region->v2d.cur.xmax ||
+      new_active_node->runtime->totr.ymax < region->v2d.cur.ymin ||
+      new_active_node->runtime->totr.ymin > region->v2d.cur.ymax) {
+    const int smooth_viewtx = WM_operator_smooth_viewtx_get(op);
+    space_node_view_flag(*C, *snode, *region, NODE_SELECT, smooth_viewtx);
   }
 
   return OPERATOR_FINISHED;