avfiltergraph: add avfilter_graph_request_oldest().

Keep a heap of all sink links ordered by timestamps.

5 files changed, 158 insertions, 8 deletions

diff --git a/libavfilter/avfilter.c b/libavfilter/avfilter.c
index 28c2599d0e..6bc66d0248 100644
--- a/libavfilter/avfilter.c
+++ b/libavfilter/avfilter.c
@@ -278,6 +278,8 @@ int avfilter_config_links(AVFilterContext *filter)
 
         if (!link) continue;
 
+        link->current_pts = AV_NOPTS_VALUE;
+
         switch (link->init_state) {
         case AVLINK_INIT:
             continue;
@@ -568,6 +570,15 @@ int avfilter_poll_frame(AVFilterLink *link)
     return min;
 }
 
+static void update_link_current_pts(AVFilterLink *link)
+{
+    if (link->cur_buf->pts == AV_NOPTS_VALUE)
+        return;
+    link->current_pts =  link->cur_buf->pts; /* TODO use duration */
+    if (link->graph && link->age_index >= 0)
+        ff_avfilter_graph_update_heap(link->graph, link);
+}
+
 /* XXX: should we do the duplicating of the picture ref here, instead of
  * forcing the source filter to do it? */
 void avfilter_start_frame(AVFilterLink *link, AVFilterBufferRef *picref)
@@ -608,6 +619,7 @@ void avfilter_start_frame(AVFilterLink *link, AVFilterBufferRef *picref)
     }
 
     start_frame(link, link->cur_buf);
+    update_link_current_pts(link);
 }
 
 void avfilter_end_frame(AVFilterLink *link)
@@ -712,6 +724,7 @@ void avfilter_filter_samples(AVFilterLink *link, AVFilterBufferRef *samplesref)
         link->cur_buf = samplesref;
 
     filter_samples(link, link->cur_buf);
+    update_link_current_pts(link);
 }
 
 #define MAX_REGISTERED_AVFILTERS_NB 128
diff --git a/libavfilter/avfilter.h b/libavfilter/avfilter.h
index b0b8cd098a..ae296cbef3 100644
--- a/libavfilter/avfilter.h
+++ b/libavfilter/avfilter.h
@@ -696,6 +696,23 @@ struct AVFilterLink {
      */
     struct AVFilterGraph *graph;
 
+    /**
+     * Current timestamp of the link, as defined by the most recent
+     * frame(s), in AV_TIME_BASE units.
+     */
+    int64_t current_pts;
+
+    /**
+     * Private fields
+     *
+     * The following fields are for internal use only.
+     * Their type, offset, number and semantic can change without notice.
+     */
+
+    /**
+     * Index in the age array.
+     */
+    int age_index;
 };
 
 /**
diff --git a/libavfilter/avfiltergraph.c b/libavfilter/avfiltergraph.c
index e46ace5c19..ef597ddf7f 100644
--- a/libavfilter/avfiltergraph.c
+++ b/libavfilter/avfiltergraph.c
@@ -24,6 +24,7 @@
 #include <string.h>
 
 #include "libavutil/audioconvert.h"
+#include "libavutil/avassert.h"
 #include "libavutil/pixdesc.h"
 #include "avfilter.h"
 #include "avfiltergraph.h"
@@ -374,19 +375,46 @@ int ff_avfilter_graph_config_formats(AVFilterGraph *graph, AVClass *log_ctx)
     return 0;
 }
 
-static void ff_avfilter_graph_config_pointers(AVFilterGraph *graph,
-                                              AVClass *log_ctx)
+static int ff_avfilter_graph_config_pointers(AVFilterGraph *graph,
+                                             AVClass *log_ctx)
 {
-    unsigned i, j;;
+    unsigned i, j;
+    int sink_links_count = 0, n = 0;
     AVFilterContext *f;
+    AVFilterLink **sinks;
 
     for (i = 0; i < graph->filter_count; i++) {
         f = graph->filters[i];
-        for (j = 0; j < f->input_count; j++)
-            f->inputs[j]->graph = graph;
-        for (j = 0; j < f->output_count; j++)
-            f->outputs[j]->graph = graph;
+        for (j = 0; j < f->input_count; j++) {
+            f->inputs[j]->graph     = graph;
+            f->inputs[j]->age_index = -1;
+        }
+        for (j = 0; j < f->output_count; j++) {
+            f->outputs[j]->graph    = graph;
+            f->outputs[j]->age_index= -1;
+        }
+        if (!f->output_count) {
+            if (f->input_count > INT_MAX - sink_links_count)
+                return AVERROR(EINVAL);
+            sink_links_count += f->input_count;
+        }
     }
+    sinks = av_calloc(sink_links_count, sizeof(*sinks));
+    if (!sinks)
+        return AVERROR(ENOMEM);
+    for (i = 0; i < graph->filter_count; i++) {
+        f = graph->filters[i];
+        if (!f->output_count) {
+            for (j = 0; j < f->input_count; j++) {
+                sinks[n] = f->inputs[j];
+                f->inputs[j]->age_index = n++;
+            }
+        }
+    }
+    av_assert0(n == sink_links_count);
+    graph->sink_links       = sinks;
+    graph->sink_links_count = sink_links_count;
+    return 0;
 }
 
 int avfilter_graph_config(AVFilterGraph *graphctx, void *log_ctx)
@@ -399,7 +427,8 @@ int avfilter_graph_config(AVFilterGraph *graphctx, void *log_ctx)
         return ret;
     if ((ret = ff_avfilter_graph_config_links(graphctx, log_ctx)))
         return ret;
-    ff_avfilter_graph_config_pointers(graphctx, log_ctx);
+    if ((ret = ff_avfilter_graph_config_pointers(graphctx, log_ctx)))
+        return ret;
 
     return 0;
 }
@@ -461,3 +490,65 @@ int avfilter_graph_queue_command(AVFilterGraph *graph, const char *target, const
 
     return 0;
 }
+
+static void heap_bubble_up(AVFilterGraph *graph,
+                           AVFilterLink *link, int index)
+{
+    AVFilterLink **links = graph->sink_links;
+
+    while (index) {
+        int parent = (index - 1) >> 1;
+        if (links[parent]->current_pts >= link->current_pts)
+            break;
+        links[index] = links[parent];
+        links[index]->age_index = index;
+        index = parent;
+    }
+    links[index] = link;
+    link->age_index = index;
+}
+
+static void heap_bubble_down(AVFilterGraph *graph,
+                             AVFilterLink *link, int index)
+{
+    AVFilterLink **links = graph->sink_links;
+
+    while (1) {
+        int child = 2 * index + 1;
+        if (child >= graph->sink_links_count)
+            break;
+        if (child + 1 < graph->sink_links_count &&
+            links[child + 1]->current_pts < links[child]->current_pts)
+            child++;
+        if (link->current_pts < links[child]->current_pts)
+            break;
+        links[index] = links[child];
+        links[index]->age_index = index;
+        index = child;
+    }
+    links[index] = link;
+    link->age_index = index;
+}
+
+void ff_avfilter_graph_update_heap(AVFilterGraph *graph, AVFilterLink *link)
+{
+    heap_bubble_up  (graph, link, link->age_index);
+    heap_bubble_down(graph, link, link->age_index);
+}
+
+
+int avfilter_graph_request_oldest(AVFilterGraph *graph)
+{
+    while (graph->sink_links_count) {
+        AVFilterLink *oldest = graph->sink_links[0];
+        int r = avfilter_request_frame(oldest);
+        if (r != AVERROR_EOF)
+            return r;
+        /* EOF: remove the link from the heap */
+        if (oldest->age_index < --graph->sink_links_count)
+            heap_bubble_down(graph, graph->sink_links[graph->sink_links_count],
+                             oldest->age_index);
+        oldest->age_index = -1;
+    }
+    return AVERROR_EOF;
+}
diff --git a/libavfilter/avfiltergraph.h b/libavfilter/avfiltergraph.h
index 2c612b481d..b003795750 100644
--- a/libavfilter/avfiltergraph.h
+++ b/libavfilter/avfiltergraph.h
@@ -33,6 +33,16 @@ typedef struct AVFilterGraph {
     AVFilterContext **filters;
 
     char *scale_sws_opts; ///< sws options to use for the auto-inserted scale filters
+
+    /**
+     * Private fields
+     *
+     * The following fields are for internal use only.
+     * Their type, offset, number and semantic can change without notice.
+     */
+
+    AVFilterLink **sink_links;
+    int sink_links_count;
 } AVFilterGraph;
 
 /**
@@ -221,4 +231,18 @@ int avfilter_graph_queue_command(AVFilterGraph *graph, const char *target, const
  */
 char *avfilter_graph_dump(AVFilterGraph *graph, const char *options);
 
+/**
+ * Request a frame on the oldest sink link.
+ *
+ * If the request returns AVERROR_EOF, try the next.
+ *
+ * Note that this function is not meant to be the sole scheduling mechanism
+ * of a filtergraph, only a convenience function to help drain a filtergraph
+ * in a balanced way under normal circumstances.
+ *
+ * @return  the return value of avfilter_request_frame,
+ *          or AVERROR_EOF of all links returned AVERROR_EOF.
+ */
+int avfilter_graph_request_oldest(AVFilterGraph *graph);
+
 #endif /* AVFILTER_AVFILTERGRAPH_H */
diff --git a/libavfilter/internal.h b/libavfilter/internal.h
index 575bcff364..47d735182d 100644
--- a/libavfilter/internal.h
+++ b/libavfilter/internal.h
@@ -65,6 +65,11 @@ int ff_avfilter_graph_config_links(AVFilterGraph *graphctx, AVClass *log_ctx);
  */
 int ff_avfilter_graph_config_formats(AVFilterGraph *graphctx, AVClass *log_ctx);
 
+/**
+ * Update the position of a link in the age heap.
+ */
+void ff_avfilter_graph_update_heap(AVFilterGraph *graph, AVFilterLink *link);
+
 /** default handler for freeing audio/video buffer when there are no references left */
 void ff_avfilter_default_free_buffer(AVFilterBuffer *buf);