summaryrefslogtreecommitdiffstats
path: root/flow/gsl/gslopschedule.c
diff options
context:
space:
mode:
Diffstat (limited to 'flow/gsl/gslopschedule.c')
-rw-r--r--flow/gsl/gslopschedule.c582
1 files changed, 582 insertions, 0 deletions
diff --git a/flow/gsl/gslopschedule.c b/flow/gsl/gslopschedule.c
new file mode 100644
index 0000000..9102a41
--- /dev/null
+++ b/flow/gsl/gslopschedule.c
@@ -0,0 +1,582 @@
+/* GSL Engine - Flow module operation engine
+ * Copyright (C) 2001 Tim Janik
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General
+ * Public License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+#include "gslopschedule.h"
+
+
+#include "gslcommon.h"
+
+
+/* --- functions --- */
+EngineSchedule*
+_engine_schedule_new (void)
+{
+ EngineSchedule *sched = gsl_new_struct0 (EngineSchedule, 1);
+
+ sched->n_items = 0;
+ sched->leaf_levels = 0;
+ sched->nodes = NULL;
+ sched->cycles = NULL;
+ sched->secured = FALSE;
+ sched->in_pqueue = FALSE;
+ sched->cur_leaf_level = ~0;
+ sched->cur_node = NULL;
+ sched->cur_cycle = NULL;
+
+ return sched;
+}
+
+static inline void
+unschedule_node (EngineSchedule *sched,
+ EngineNode *node)
+{
+ guint leaf_level;
+
+ g_return_if_fail (ENGINE_NODE_IS_SCHEDULED (node) == TRUE);
+ leaf_level = node->sched_leaf_level;
+ g_return_if_fail (leaf_level <= sched->leaf_levels);
+ g_return_if_fail (sched->n_items > 0);
+
+ SCHED_DEBUG ("unschedule_node(%p,%u)", node, leaf_level);
+ sched->nodes[leaf_level] = gsl_ring_remove (sched->nodes[leaf_level], node);
+ node->sched_leaf_level = 0;
+ node->sched_tag = FALSE;
+ if (node->flow_jobs)
+ _engine_mnl_reorder (node);
+ sched->n_items--;
+}
+
+static inline void
+unschedule_cycle (EngineSchedule *sched,
+ GslRing *ring)
+{
+ guint leaf_level;
+ GslRing *walk;
+
+ g_return_if_fail (ENGINE_NODE_IS_SCHEDULED (ENGINE_NODE (ring->data)) == TRUE);
+ leaf_level = ENGINE_NODE (ring->data)->sched_leaf_level;
+ g_return_if_fail (leaf_level <= sched->leaf_levels);
+ g_return_if_fail (sched->n_items > 0);
+
+ SCHED_DEBUG ("unschedule_cycle(%p,%u,%p)", ring->data, leaf_level, ring);
+ sched->nodes[leaf_level] = gsl_ring_remove (sched->nodes[leaf_level], ring);
+ for (walk = ring; walk; walk = gsl_ring_walk (ring, walk))
+ {
+ EngineNode *node = walk->data;
+
+ if (!ENGINE_NODE_IS_SCHEDULED (node))
+ g_warning ("node(%p) in schedule ring(%p) is untagged", node, ring);
+ node->sched_leaf_level = 0;
+ node->sched_tag = FALSE;
+ if (node->flow_jobs)
+ _engine_mnl_reorder (node);
+ }
+ sched->n_items--;
+}
+
+static void
+_engine_schedule_debug_dump (EngineSchedule *sched)
+{
+ g_printerr ("sched(%p) = {\n", sched);
+ if (sched)
+ {
+ guint i;
+
+ g_printerr (" n_items=%u, leaf_levels=%u, secured=%u,\n",
+ sched->n_items, sched->leaf_levels, sched->secured);
+ g_printerr (" in_pqueue=%u, cur_leaf_level=%u,\n",
+ sched->in_pqueue, sched->cur_leaf_level);
+ g_printerr (" cur_node=%p, cur_cycle=%p,\n",
+ sched->cur_node, sched->cur_cycle);
+ for (i = 0; i < sched->leaf_levels; i++)
+ {
+ GslRing *ring, *head = sched->nodes[i];
+
+ if (!head)
+ continue;
+ g_printerr (" { leaf_level=%u:", i);
+ for (ring = head; ring; ring = gsl_ring_walk (head, ring))
+ g_printerr (" node(%p(tag:%u))", ring->data, ((EngineNode*) ring->data)->sched_tag);
+ g_printerr (" },\n");
+ }
+ }
+ g_printerr ("};\n");
+}
+
+
+void
+_engine_schedule_clear (EngineSchedule *sched)
+{
+ guint i;
+
+ g_return_if_fail (sched != NULL);
+ g_return_if_fail (sched->secured == FALSE);
+ g_return_if_fail (sched->in_pqueue == FALSE);
+
+ for (i = 0; i < sched->leaf_levels; i++)
+ {
+ /* FIXME: each unschedule operation is a list walk, while we
+ * could easily leave the rings alone and free them as a whole
+ */
+ while (sched->nodes[i])
+ unschedule_node (sched, sched->nodes[i]->data);
+ while (sched->cycles[i])
+ unschedule_cycle (sched, sched->cycles[i]->data);
+ }
+ g_return_if_fail (sched->n_items == 0);
+}
+
+void
+_engine_schedule_destroy (EngineSchedule *sched)
+{
+ g_return_if_fail (sched != NULL);
+ g_return_if_fail (sched->secured == FALSE);
+ g_return_if_fail (sched->in_pqueue == FALSE);
+
+ _engine_schedule_clear (sched);
+ g_free (sched->nodes);
+ g_free (sched->cycles);
+ gsl_delete_struct (EngineSchedule, sched);
+}
+
+static void
+_engine_schedule_grow (EngineSchedule *sched,
+ guint leaf_level)
+{
+ guint ll = 1 << g_bit_storage (leaf_level); /* power2 growth alignment, ll >= leaf_level+1 */
+
+ if (sched->leaf_levels < ll)
+ {
+ guint i = sched->leaf_levels;
+
+ sched->leaf_levels = ll;
+ sched->nodes = g_renew (GslRing*, sched->nodes, sched->leaf_levels);
+ sched->cycles = g_renew (GslRing*, sched->cycles, sched->leaf_levels);
+ for (; i < sched->leaf_levels; i++)
+ {
+ sched->nodes[i] = NULL;
+ sched->cycles[i] = NULL;
+ }
+ }
+}
+
+void
+_engine_schedule_node (EngineSchedule *sched,
+ EngineNode *node,
+ guint leaf_level)
+{
+ g_return_if_fail (sched != NULL);
+ g_return_if_fail (sched->secured == FALSE);
+ g_return_if_fail (node != NULL);
+ g_return_if_fail (!ENGINE_NODE_IS_SCHEDULED (node));
+
+ SCHED_DEBUG ("schedule_node(%p,%u)", node, leaf_level);
+ node->sched_leaf_level = leaf_level;
+ node->sched_tag = TRUE;
+ if (node->flow_jobs)
+ _engine_mnl_reorder (node);
+ _engine_schedule_grow (sched, leaf_level);
+ /* could do 3-stage scheduling by expensiveness */
+ sched->nodes[leaf_level] = (ENGINE_NODE_IS_EXPENSIVE (node) ? gsl_ring_prepend : gsl_ring_append) (sched->nodes[leaf_level], node);
+ sched->n_items++;
+}
+
+void
+_engine_schedule_cycle (EngineSchedule *sched,
+ GslRing *cycle_nodes,
+ guint leaf_level)
+{
+ GslRing *walk;
+
+ g_return_if_fail (sched != NULL);
+ g_return_if_fail (sched->secured == FALSE);
+ g_return_if_fail (cycle_nodes != NULL);
+
+ for (walk = cycle_nodes; walk; walk = gsl_ring_walk (cycle_nodes, walk))
+ {
+ EngineNode *node = walk->data;
+
+ g_return_if_fail (!ENGINE_NODE_IS_SCHEDULED (node));
+ node->sched_leaf_level = leaf_level;
+ node->sched_tag = TRUE;
+ if (node->flow_jobs)
+ _engine_mnl_reorder (node);
+ }
+ _engine_schedule_grow (sched, leaf_level);
+ sched->cycles[leaf_level] = gsl_ring_prepend (sched->cycles[leaf_level], cycle_nodes);
+ sched->n_items++;
+}
+
+void
+_engine_schedule_restart (EngineSchedule *sched)
+{
+ g_return_if_fail (sched != NULL);
+ g_return_if_fail (sched->secured == TRUE);
+ g_return_if_fail (sched->cur_leaf_level == sched->leaf_levels);
+ g_return_if_fail (sched->cur_node == NULL);
+ g_return_if_fail (sched->cur_cycle == NULL);
+
+ sched->cur_leaf_level = 0;
+ if (sched->leaf_levels > 0)
+ {
+ sched->cur_node = sched->nodes[0];
+ sched->cur_cycle = sched->cycles[0];
+ }
+}
+
+void
+_engine_schedule_secure (EngineSchedule *sched)
+{
+ g_return_if_fail (sched != NULL);
+ g_return_if_fail (sched->secured == FALSE);
+
+ sched->secured = TRUE;
+ sched->cur_leaf_level = sched->leaf_levels;
+
+ if (gsl_debug_check (GSL_MSG_SCHED))
+ _engine_schedule_debug_dump (sched);
+}
+
+static void
+schedule_advance (EngineSchedule *sched)
+{
+ while (!sched->cur_node && !sched->cur_cycle && sched->cur_leaf_level < sched->leaf_levels)
+ {
+ sched->cur_leaf_level += 1;
+ if (sched->cur_leaf_level < sched->leaf_levels)
+ {
+ sched->cur_node = sched->nodes[sched->cur_leaf_level];
+ sched->cur_cycle = sched->cycles[sched->cur_leaf_level];
+ }
+ }
+}
+
+EngineNode*
+_engine_schedule_pop_node (EngineSchedule *sched)
+{
+ g_return_val_if_fail (sched != NULL, NULL);
+ g_return_val_if_fail (sched->secured == TRUE, NULL);
+ g_return_val_if_fail (sched->cur_leaf_level <= sched->leaf_levels, NULL);
+
+ do
+ {
+ guint leaf_level = sched->cur_leaf_level;
+
+ if (sched->cur_node)
+ {
+ EngineNode *node = sched->cur_node->data;
+
+ sched->cur_node = gsl_ring_walk (sched->nodes[leaf_level], sched->cur_node);
+ return node;
+ }
+ schedule_advance (sched);
+ }
+ while (sched->cur_node);
+
+ /* nothing to hand out, either we're empty or still have cycles pending */
+ return NULL;
+}
+
+GslRing*
+_engine_schedule_pop_cycle (EngineSchedule *sched)
+{
+ g_return_val_if_fail (sched != NULL, NULL);
+ g_return_val_if_fail (sched->secured == TRUE, NULL);
+ g_return_val_if_fail (sched->cur_leaf_level <= sched->leaf_levels, NULL);
+
+ do
+ {
+ guint leaf_level = sched->cur_leaf_level;
+
+ if (sched->cur_cycle)
+ {
+ GslRing *cycle = sched->cur_cycle->data;
+
+ sched->cur_cycle = gsl_ring_walk (sched->cycles[leaf_level], sched->cur_cycle);
+ return cycle;
+ }
+ schedule_advance (sched);
+ }
+ while (sched->cur_cycle);
+
+ /* nothing to hand out, either we're empty or still have nodes pending */
+ return NULL;
+}
+
+void
+_engine_schedule_unsecure (EngineSchedule *sched)
+{
+ g_return_if_fail (sched != NULL);
+ g_return_if_fail (sched->secured == TRUE);
+ g_return_if_fail (sched->in_pqueue == FALSE);
+ g_return_if_fail (sched->cur_leaf_level == sched->leaf_levels);
+ g_return_if_fail (sched->cur_node == NULL);
+ g_return_if_fail (sched->cur_cycle == NULL);
+
+ sched->secured = FALSE;
+ sched->cur_leaf_level = ~0;
+}
+
+
+/* --- depth scheduling --- */
+static GslRing*
+merge_untagged_node_lists_uniq (GslRing *ring1,
+ GslRing *ring2)
+{
+ GslRing *walk;
+
+ /* paranoid, ensure all nodes are untagged */
+ for (walk = ring2; walk; walk = gsl_ring_walk (ring2, walk))
+ {
+ EngineNode *node = walk->data;
+
+ g_assert (node->sched_router_tag == FALSE);
+ }
+
+ /* tag all nodes in list first */
+ for (walk = ring1; walk; walk = gsl_ring_walk (ring1, walk))
+ {
+ EngineNode *node = walk->data;
+
+ g_assert (node->sched_router_tag == FALSE); /* paranoid check */
+ node->sched_router_tag = TRUE;
+ }
+
+ /* merge list with missing (untagged) nodes */
+ for (walk = ring2; walk; walk = gsl_ring_walk (ring2, walk))
+ {
+ EngineNode *node = walk->data;
+
+ if (node->sched_router_tag == FALSE)
+ ring1 = gsl_ring_append (ring1, node);
+ }
+
+ /* untag all nodes */
+ for (walk = ring1; walk; walk = gsl_ring_walk (ring1, walk))
+ {
+ EngineNode *node = walk->data;
+
+ node->sched_router_tag = FALSE;
+ }
+ for (walk = ring2; walk; walk = gsl_ring_walk (ring2, walk))
+ {
+ EngineNode *node = walk->data;
+
+ node->sched_router_tag = FALSE;
+ }
+ gsl_ring_free (ring2);
+ return ring1;
+}
+
+static gboolean
+resolve_cycle (EngineCycle *cycle,
+ EngineNode *node,
+ GslRing **cycle_nodes_p)
+{
+ if (node != cycle->last)
+ return FALSE;
+ if (!cycle->seen_deferred_node)
+ {
+ g_error ("cycle without delay module: (%p)", cycle);
+ }
+ *cycle_nodes_p = merge_untagged_node_lists_uniq (*cycle_nodes_p, cycle->nodes);
+ cycle->nodes = NULL;
+ cycle->last = NULL;
+ return TRUE;
+}
+
+static gboolean
+master_resolve_cycles (EngineQuery *query,
+ EngineNode *node)
+{
+ GslRing *walk;
+ gboolean all_resolved = TRUE;
+
+ g_assert (query->cycles != NULL); /* paranoid */
+
+ walk = query->cycles;
+ while (walk)
+ {
+ GslRing *next = gsl_ring_walk (query->cycles, walk);
+ EngineCycle *cycle = walk->data;
+
+ if (resolve_cycle (cycle, node, &query->cycle_nodes))
+ {
+ g_assert (cycle->last == NULL); /* paranoid */
+ g_assert (cycle->nodes == NULL); /* paranoid */
+
+ gsl_delete_struct (EngineCycle, cycle);
+ query->cycles = gsl_ring_remove_node (query->cycles, walk);
+ }
+ else
+ all_resolved = FALSE;
+ walk = next;
+ }
+ if (all_resolved)
+ g_assert (query->cycles == NULL); /* paranoid */
+ return all_resolved;
+}
+
+static void
+query_add_cycle (EngineQuery *query,
+ EngineNode *dep,
+ EngineNode *node)
+{
+ EngineCycle *cycle = gsl_new_struct0 (EngineCycle, 1);
+
+ cycle->last = dep;
+ cycle->nodes = gsl_ring_prepend (NULL, node);
+ cycle->seen_deferred_node = ENGINE_NODE_IS_DEFERRED (node); /* dep will be checked when added to nodes */
+ query->cycles = gsl_ring_append (query->cycles, cycle);
+}
+
+static void
+query_merge_cycles (EngineQuery *query,
+ EngineQuery *child_query,
+ EngineNode *node)
+{
+ GslRing *walk;
+
+ g_assert (child_query->cycles != NULL); /* paranoid */
+
+ /* add node to all child cycles */
+ for (walk = child_query->cycles; walk; walk = gsl_ring_walk (child_query->cycles, walk))
+ {
+ EngineCycle *cycle = walk->data;
+
+ cycle->nodes = gsl_ring_prepend (cycle->nodes, node);
+ cycle->seen_deferred_node |= ENGINE_NODE_IS_DEFERRED (node);
+ }
+
+ /* merge child cycles into ours */
+ query->cycles = gsl_ring_concat (query->cycles, child_query->cycles);
+ child_query->cycles = NULL;
+
+ /* merge childs cycle nodes from resolved cycles into ours */
+ query->cycle_nodes = merge_untagged_node_lists_uniq (query->cycle_nodes, child_query->cycle_nodes);
+ child_query->cycle_nodes = NULL;
+}
+
+static void
+subschedule_query_node (EngineSchedule *schedule,
+ EngineNode *node,
+ EngineQuery *query)
+{
+ guint i, j, leaf_level = 0;
+
+ g_return_if_fail (node->sched_router_tag == FALSE);
+
+ SCHED_DEBUG ("start_query(%p)", node);
+ node->sched_router_tag = TRUE;
+ for (i = 0; i < ENGINE_NODE_N_ISTREAMS (node); i++)
+ {
+ EngineNode *child = node->inputs[i].src_node;
+
+ if (!child)
+ continue;
+ else if (ENGINE_NODE_IS_SCHEDULED (child))
+ {
+ leaf_level = MAX (leaf_level, child->sched_leaf_level + 1);
+ continue;
+ }
+ else if (child->sched_router_tag) /* cycle */
+ {
+ query_add_cycle (query, child, node);
+ }
+ else /* nice boy ;) */
+ {
+ EngineQuery child_query = { 0, };
+
+ subschedule_query_node (schedule, child, &child_query);
+ leaf_level = MAX (leaf_level, child_query.leaf_level + 1);
+ if (!child_query.cycles)
+ {
+ g_assert (child_query.cycle_nodes == NULL); /* paranoid */
+ _engine_schedule_node (schedule, child, child_query.leaf_level);
+ }
+ else if (master_resolve_cycles (&child_query, child))
+ {
+ g_assert (child == child_query.cycle_nodes->data); /* paranoid */
+ _engine_schedule_cycle (schedule, child_query.cycle_nodes, child_query.leaf_level);
+ child_query.cycle_nodes = NULL;
+ }
+ else
+ query_merge_cycles (query, &child_query, node);
+ g_assert (child_query.cycles == NULL); /* paranoid */
+ g_assert (child_query.cycle_nodes == NULL); /* paranoid */
+ }
+ }
+ for (j = 0; j < ENGINE_NODE_N_JSTREAMS (node); j++)
+ for (i = 0; i < node->module.jstreams[j].n_connections; i++)
+ {
+ EngineNode *child = node->jinputs[j][i].src_node;
+
+ if (ENGINE_NODE_IS_SCHEDULED (child))
+ {
+ leaf_level = MAX (leaf_level, child->sched_leaf_level + 1);
+ continue;
+ }
+ else if (child->sched_router_tag) /* cycle */
+ {
+ query_add_cycle (query, child, node);
+ }
+ else /* nice boy ;) */
+ {
+ EngineQuery child_query = { 0, };
+
+ subschedule_query_node (schedule, child, &child_query);
+ leaf_level = MAX (leaf_level, child_query.leaf_level + 1);
+ if (!child_query.cycles)
+ {
+ g_assert (child_query.cycle_nodes == NULL); /* paranoid */
+ _engine_schedule_node (schedule, child, child_query.leaf_level);
+ }
+ else if (master_resolve_cycles (&child_query, child))
+ {
+ g_assert (child == child_query.cycle_nodes->data); /* paranoid */
+ _engine_schedule_cycle (schedule, child_query.cycle_nodes, child_query.leaf_level);
+ child_query.cycle_nodes = NULL;
+ }
+ else
+ query_merge_cycles (query, &child_query, node);
+ g_assert (child_query.cycles == NULL); /* paranoid */
+ g_assert (child_query.cycle_nodes == NULL); /* paranoid */
+ }
+ }
+ query->leaf_level = leaf_level;
+ node->counter = GSL_TICK_STAMP;
+ node->sched_router_tag = FALSE;
+ SCHED_DEBUG ("end_query(%p)", node);
+}
+
+void
+_engine_schedule_consumer_node (EngineSchedule *schedule,
+ EngineNode *node)
+{
+ EngineQuery query = { 0, };
+
+ g_return_if_fail (schedule != NULL);
+ g_return_if_fail (schedule->secured == FALSE);
+ g_return_if_fail (node != NULL);
+ g_return_if_fail (ENGINE_NODE_IS_CONSUMER (node));
+
+ subschedule_query_node (schedule, node, &query);
+ g_assert (query.cycles == NULL); /* paranoid */
+ g_assert (query.cycle_nodes == NULL); /* paranoid */
+ _engine_schedule_node (schedule, node, query.leaf_level);
+}
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-14 22:02:22 +0000