[gegl] graph: allow terminating GeglVisitor traversal early

[N/A <ell src gnome org>]

commit a544de33634fa63a7f92d4af40de594aab5754e1
Author: Ell <ell_se yahoo com>
Date:   Thu Nov 9 14:02:18 2017 -0500

    graph: allow terminating GeglVisitor traversal early
    
    Have GeglVisitor::visit_{pad,node}() return gboolean, instead of
    void.  Returning TRUE from these functions terminates traversal
    early.  This is useful, e.g., when searching a specific node in a
    graph.
    
    Have gegl_visitor_{dfs,bfs}_traverse() return a gboolean, instead
    of void, indicating whether traversal was terminated early.  This
    is useful, e.g., to determine whether the node was found.
    
    Adapt the rest of the code to the changes.

 gegl/gegl-dot-visitor.c          |   22 ++++++----
 gegl/graph/gegl-node.c           |    6 +-
 gegl/graph/gegl-pad.c            |    6 +-
 gegl/graph/gegl-visitable.c      |    4 +-
 gegl/graph/gegl-visitable.h      |    4 +-
 gegl/graph/gegl-visitor.c        |   84 +++++++++++++++++++++++++------------
 gegl/graph/gegl-visitor.h        |   29 +++++++------
 gegl/process/gegl-list-visitor.c |   12 +++--
 8 files changed, 102 insertions(+), 65 deletions(-)
---
diff --git a/gegl/gegl-dot-visitor.c b/gegl/gegl-dot-visitor.c
index 8ea8d74..da1de4f 100644
--- a/gegl/gegl-dot-visitor.c
+++ b/gegl/gegl-dot-visitor.c
@@ -35,11 +35,11 @@ struct _GeglDotVisitorPriv
 };
 
 
-static void gegl_dot_visitor_class_init (GeglDotVisitorClass *klass);
-static void gegl_dot_visitor_visit_node (GeglVisitor         *self,
-                                         GeglNode            *node);
-static void gegl_dot_visitor_visit_pad  (GeglVisitor         *self,
-                                         GeglPad             *pad);
+static void       gegl_dot_visitor_class_init (GeglDotVisitorClass *klass);
+static gboolean   gegl_dot_visitor_visit_node (GeglVisitor         *self,
+                                               GeglNode            *node);
+static gboolean   gegl_dot_visitor_visit_pad  (GeglVisitor         *self,
+                                               GeglPad             *pad);
 
 
 G_DEFINE_TYPE (GeglDotVisitor, gegl_dot_visitor, GEGL_TYPE_VISITOR)
@@ -71,20 +71,22 @@ gegl_dot_visitor_set_string_to_append (GeglDotVisitor *self,
   self->priv->string_to_append = string_to_append;
 }
 
-static void
+static gboolean
 gegl_dot_visitor_visit_node (GeglVisitor *visitor,
                              GeglNode    *node)
 {
   GeglDotVisitor *self = GEGL_DOT_VISITOR (visitor);
 
-  g_return_if_fail (self->priv->string_to_append != NULL);
+  g_return_val_if_fail (self->priv->string_to_append != NULL, FALSE);
 
   GEGL_VISITOR_CLASS (gegl_dot_visitor_parent_class)->visit_node (visitor, node);
 
   gegl_dot_util_add_node (self->priv->string_to_append, node);
+
+  return FALSE;
 }
 
-static void
+static gboolean
 gegl_dot_visitor_visit_pad (GeglVisitor *visitor,
                             GeglPad     *pad)
 {
@@ -93,7 +95,7 @@ gegl_dot_visitor_visit_pad (GeglVisitor *visitor,
   GSList         *iter;
   GSList         *pad_iter;
 
-  g_return_if_fail (self->priv->string_to_append != NULL);
+  g_return_val_if_fail (self->priv->string_to_append != NULL, FALSE);
 
   GEGL_VISITOR_CLASS (gegl_dot_visitor_parent_class)->visit_pad (visitor, pad);
 
@@ -115,4 +117,6 @@ gegl_dot_visitor_visit_pad (GeglVisitor *visitor,
     }
 
   g_slist_free (pads);
+
+  return FALSE;
 }
diff --git a/gegl/graph/gegl-node.c b/gegl/graph/gegl-node.c
index 3de6d83..58df4a9 100644
--- a/gegl/graph/gegl-node.c
+++ b/gegl/graph/gegl-node.c
@@ -98,7 +98,7 @@ static GeglConnection *gegl_node_find_connection          (GeglNode      *sink,
                                                            GeglPad       *sink_pad);
 static void            gegl_node_visitable_iface_init     (gpointer       ginterface,
                                                            gpointer       interface_data);
-static void            gegl_node_visitable_accept         (GeglVisitable *visitable,
+static gboolean        gegl_node_visitable_accept         (GeglVisitable *visitable,
                                                            GeglVisitor   *visitor);
 static GSList*         gegl_node_visitable_depends_on     (GeglVisitable *visitable);
 static void            gegl_node_set_operation_object     (GeglNode      *self,
@@ -1077,11 +1077,11 @@ gegl_node_dump_depends_on (GeglNode *self)
   g_slist_free (depends_on);
 }
 
-static void
+static gboolean
 gegl_node_visitable_accept (GeglVisitable *visitable,
                             GeglVisitor   *visitor)
 {
-  gegl_visitor_visit_node (visitor, (GeglNode *) visitable);
+  return gegl_visitor_visit_node (visitor, (GeglNode *) visitable);
 }
 
 static GSList *
diff --git a/gegl/graph/gegl-pad.c b/gegl/graph/gegl-pad.c
index 0ef9fe3..02754bd 100644
--- a/gegl/graph/gegl-pad.c
+++ b/gegl/graph/gegl-pad.c
@@ -36,7 +36,7 @@ static void       gegl_pad_init            (GeglPad       *self);
 static void       finalize                 (GObject       *gobject);
 static void       visitable_init           (gpointer       ginterface,
                                             gpointer       interface_data);
-static void       visitable_accept         (GeglVisitable *visitable,
+static gboolean   visitable_accept         (GeglVisitable *visitable,
                                             GeglVisitor   *visitor);
 static GSList   * visitable_depends_on     (GeglVisitable *visitable);
 
@@ -249,11 +249,11 @@ gegl_pad_is_input (GeglPad *self)
   return GEGL_PARAM_PAD_INPUT & self->param_spec->flags;
 }
 
-static void
+static gboolean
 visitable_accept (GeglVisitable *visitable,
                   GeglVisitor   *visitor)
 {
-  gegl_visitor_visit_pad (visitor, (GeglPad*) (visitable));
+  return gegl_visitor_visit_pad (visitor, (GeglPad*) (visitable));
 }
 
 static GSList *
diff --git a/gegl/graph/gegl-visitable.c b/gegl/graph/gegl-visitable.c
index a0f6924..c170498 100644
--- a/gegl/graph/gegl-visitable.c
+++ b/gegl/graph/gegl-visitable.c
@@ -57,7 +57,7 @@ gegl_visitable_get_type (void)
   return type;
 }
 
-void
+gboolean
 gegl_visitable_accept (GeglVisitable *interface,
                        GeglVisitor   *visitor)
 {
@@ -67,7 +67,7 @@ gegl_visitable_accept (GeglVisitable *interface,
 
   interface_class = GEGL_VISITABLE_GET_CLASS (interface);
 
-  interface_class->accept (interface, visitor);
+  return interface_class->accept (interface, visitor);
 }
 
 GSList *
diff --git a/gegl/graph/gegl-visitable.h b/gegl/graph/gegl-visitable.h
index 55d97c9..4cddf2a 100644
--- a/gegl/graph/gegl-visitable.h
+++ b/gegl/graph/gegl-visitable.h
@@ -34,7 +34,7 @@ struct _GeglVisitableClass
 {
   GTypeInterface  base_interface;
 
-  void       (* accept)         (GeglVisitable *interface,
+  gboolean   (* accept)         (GeglVisitable *interface,
                                  GeglVisitor   *visitor);
   GSList   * (* depends_on)     (GeglVisitable *interface);
 };
@@ -42,7 +42,7 @@ struct _GeglVisitableClass
 
 GType      gegl_visitable_get_type       (void) G_GNUC_CONST;
 
-void       gegl_visitable_accept         (GeglVisitable *interface,
+gboolean   gegl_visitable_accept         (GeglVisitable *interface,
                                           GeglVisitor   *visitor);
 GSList   * gegl_visitable_depends_on     (GeglVisitable *interface);
 
diff --git a/gegl/graph/gegl-visitor.c b/gegl/graph/gegl-visitor.c
index 7144241..818e42e 100644
--- a/gegl/graph/gegl-visitor.c
+++ b/gegl/graph/gegl-visitor.c
@@ -30,14 +30,14 @@
 #include "gegl-visitable.h"
 
 
-static void   gegl_visitor_class_init        (GeglVisitorClass *klass);
-static void   gegl_visitor_init              (GeglVisitor      *self);
-static void   gegl_visitor_dfs_traverse_step (GeglVisitor      *self,
-                                              GeglVisitable    *visitable,
-                                              GHashTable       *visited_set);
-static void   gegl_visitor_bfs_init_step     (GeglVisitor      *self,
-                                              GeglVisitable    *visitable,
-                                              GHashTable       *edge_counts);
+static void       gegl_visitor_class_init        (GeglVisitorClass *klass);
+static void       gegl_visitor_init              (GeglVisitor      *self);
+static gboolean   gegl_visitor_dfs_traverse_step (GeglVisitor      *self,
+                                                  GeglVisitable    *visitable,
+                                                  GHashTable       *visited_set);
+static void       gegl_visitor_bfs_init_step     (GeglVisitor      *self,
+                                                  GeglVisitable    *visitable,
+                                                  GHashTable       *edge_counts);
 
 
 G_DEFINE_TYPE (GeglVisitor, gegl_visitor, G_TYPE_OBJECT)
@@ -56,35 +56,39 @@ gegl_visitor_init (GeglVisitor *self)
 }
 
 /* should be called by visitables, to visit a pad */
-void
+gboolean
 gegl_visitor_visit_pad (GeglVisitor *self,
                         GeglPad     *pad)
 {
   GeglVisitorClass *klass;
 
-  g_return_if_fail (GEGL_IS_VISITOR (self));
-  g_return_if_fail (GEGL_IS_PAD (pad));
+  g_return_val_if_fail (GEGL_IS_VISITOR (self), FALSE);
+  g_return_val_if_fail (GEGL_IS_PAD (pad), FALSE);
 
   klass = GEGL_VISITOR_GET_CLASS (self);
 
   if (klass->visit_pad)
-    klass->visit_pad (self, pad);
+    return klass->visit_pad (self, pad);
+  else
+    return FALSE;
 }
 
 /* should be called by visitables, to visit a node */
-void
+gboolean
 gegl_visitor_visit_node (GeglVisitor *self,
                          GeglNode    *node)
 {
   GeglVisitorClass *klass;
 
-  g_return_if_fail (GEGL_IS_VISITOR (self));
-  g_return_if_fail (GEGL_IS_NODE (node));
+  g_return_val_if_fail (GEGL_IS_VISITOR (self), FALSE);
+  g_return_val_if_fail (GEGL_IS_NODE (node), FALSE);
 
   klass = GEGL_VISITOR_GET_CLASS (self);
 
   if (klass->visit_node)
-    klass->visit_node (self, node);
+    return klass->visit_node (self, node);
+  else
+    return FALSE;
 }
 
 /**
@@ -93,24 +97,29 @@ gegl_visitor_visit_node (GeglVisitor *self,
  * @visitable: the start #GeglVisitable
  *
  * Traverse depth first starting at @visitable.
+ *
+ * Returns: %TRUE if traversal was terminated early.
  **/
-void
+gboolean
 gegl_visitor_dfs_traverse (GeglVisitor   *self,
                            GeglVisitable *visitable)
 {
   GHashTable *visited_set;
+  gboolean    result;
 
-  g_return_if_fail (GEGL_IS_VISITOR (self));
-  g_return_if_fail (GEGL_IS_VISITABLE (visitable));
+  g_return_val_if_fail (GEGL_IS_VISITOR (self), FALSE);
+  g_return_val_if_fail (GEGL_IS_VISITABLE (visitable), FALSE);
 
   visited_set = g_hash_table_new (NULL, NULL);
 
-  gegl_visitor_dfs_traverse_step (self, visitable, visited_set);
+  result = gegl_visitor_dfs_traverse_step (self, visitable, visited_set);
 
   g_hash_table_unref (visited_set);
+
+  return result;
 }
 
-static void
+static gboolean
 gegl_visitor_dfs_traverse_step (GeglVisitor   *self,
                                 GeglVisitable *visitable,
                                 GHashTable    *visited_set)
@@ -125,13 +134,24 @@ gegl_visitor_dfs_traverse_step (GeglVisitor   *self,
       GeglVisitable *dependency = iter->data;
 
       if (! g_hash_table_contains (visited_set, dependency))
-        gegl_visitor_dfs_traverse_step (self, dependency, visited_set);
+        {
+          if (gegl_visitor_dfs_traverse_step (self, dependency, visited_set))
+            {
+              g_slist_free (dependencies);
+
+              return TRUE;
+            }
+        }
     }
 
   g_slist_free (dependencies);
 
-  gegl_visitable_accept (visitable, self);
+  if (gegl_visitable_accept (visitable, self))
+    return TRUE;
+
   g_hash_table_add (visited_set, visitable);
+
+  return FALSE;
 }
 
 /**
@@ -140,16 +160,18 @@ gegl_visitor_dfs_traverse_step (GeglVisitor   *self,
  * @visitable: the root #GeglVisitable.
  *
  * Traverse breadth-first starting at @visitable.
+ *
+ * Returns: %TRUE if traversal was terminated early.
  **/
-void
+gboolean
 gegl_visitor_bfs_traverse (GeglVisitor   *self,
                            GeglVisitable *visitable)
 {
   GHashTable *edge_counts;
   GQueue      queue = G_QUEUE_INIT;
 
-  g_return_if_fail (GEGL_IS_VISITOR (self));
-  g_return_if_fail (GEGL_IS_VISITABLE (visitable));
+  g_return_val_if_fail (GEGL_IS_VISITOR (self), FALSE);
+  g_return_val_if_fail (GEGL_IS_VISITABLE (visitable), FALSE);
 
   edge_counts = g_hash_table_new (NULL, NULL);
 
@@ -162,7 +184,13 @@ gegl_visitor_bfs_traverse (GeglVisitor   *self,
       GSList *dependencies;
       GSList *iter;
 
-      gegl_visitable_accept (visitable, self);
+      if (gegl_visitable_accept (visitable, self))
+        {
+          g_queue_clear (&queue);
+          g_hash_table_unref (edge_counts);
+
+          return TRUE;
+        }
 
       dependencies = gegl_visitable_depends_on (visitable);
 
@@ -188,6 +216,8 @@ gegl_visitor_bfs_traverse (GeglVisitor   *self,
     }
 
   g_hash_table_unref (edge_counts);
+
+  return FALSE;
 }
 
 static void
diff --git a/gegl/graph/gegl-visitor.h b/gegl/graph/gegl-visitor.h
index 34ed319..4e68634 100644
--- a/gegl/graph/gegl-visitor.h
+++ b/gegl/graph/gegl-visitor.h
@@ -40,26 +40,27 @@ struct _GeglVisitor
 
 struct _GeglVisitorClass
 {
-  GObjectClass        parent_class;
+  GObjectClass  parent_class;
 
-  void (* visit_pad)  (GeglVisitor  *self,
-                       GeglPad      *pad);
-  void (* visit_node) (GeglVisitor  *self,
-                       GeglNode     *node);
+  /* these functions return TRUE to stop traversal, FALSE to continue */
+  gboolean (* visit_pad)  (GeglVisitor  *self,
+                           GeglPad      *pad);
+  gboolean (* visit_node) (GeglVisitor  *self,
+                           GeglNode     *node);
 };
 
 
-GType    gegl_visitor_get_type     (void) G_GNUC_CONST;
+GType      gegl_visitor_get_type     (void) G_GNUC_CONST;
 
-void     gegl_visitor_visit_pad    (GeglVisitor   *self,
-                                    GeglPad       *pad);
-void     gegl_visitor_visit_node   (GeglVisitor   *self,
-                                    GeglNode      *node);
+gboolean   gegl_visitor_visit_pad    (GeglVisitor   *self,
+                                      GeglPad       *pad);
+gboolean   gegl_visitor_visit_node   (GeglVisitor   *self,
+                                      GeglNode      *node);
 
-void     gegl_visitor_dfs_traverse (GeglVisitor   *self,
-                                    GeglVisitable *visitable);
-void     gegl_visitor_bfs_traverse (GeglVisitor   *self,
-                                    GeglVisitable *visitable);
+gboolean   gegl_visitor_dfs_traverse (GeglVisitor   *self,
+                                      GeglVisitable *visitable);
+gboolean   gegl_visitor_bfs_traverse (GeglVisitor   *self,
+                                      GeglVisitable *visitable);
 
 
 G_END_DECLS
diff --git a/gegl/process/gegl-list-visitor.c b/gegl/process/gegl-list-visitor.c
index ea43e84..2e5db5d 100644
--- a/gegl/process/gegl-list-visitor.c
+++ b/gegl/process/gegl-list-visitor.c
@@ -31,10 +31,10 @@
 #include "gegl-instrument.h"
 #include "operation/gegl-operation.h"
 
-static void gegl_list_visitor_class_init (GeglListVisitorClass *klass);
-static void gegl_list_visitor_visit_node (GeglVisitor          *self,
-                                          GeglNode             *node);
-static void gegl_list_visitor_finalize   (GObject              *visitor);
+static void       gegl_list_visitor_class_init (GeglListVisitorClass *klass);
+static gboolean   gegl_list_visitor_visit_node (GeglVisitor          *self,
+                                                GeglNode             *node);
+static void       gegl_list_visitor_finalize   (GObject              *visitor);
 
 G_DEFINE_TYPE (GeglListVisitor, gegl_list_visitor, GEGL_TYPE_VISITOR)
 
@@ -109,11 +109,13 @@ gegl_list_visitor_get_bfs_path (GeglListVisitor *self,
   return g_list_reverse (result);
 }
 
-static void
+static gboolean
 gegl_list_visitor_visit_node (GeglVisitor *visitor,
                               GeglNode    *node)
 {
   GeglListVisitor *list_visitor = GEGL_LIST_VISITOR(visitor);
 
   list_visitor->visit_path = g_list_prepend (list_visitor->visit_path, node);
+
+  return FALSE;
 }