[FFmpeg-devel] [PATCH 3/8] avfilter: keep a list of sink links by age.

[Nicolas George]

The data structure is currently a doubly-linked list
kept sorted using a bubble-sort.
It can be changed into a binary heap using
the same fields in the public structures.

Signed-off-by: Nicolas George <nicolas.george at normalesup.org>
---
 libavfilter/avfilter.c      |   32 ++++++++++++++++++++++++++++++++
 libavfilter/avfilter.h      |   18 ++++++++++++++++++
 libavfilter/avfiltergraph.c |   12 +++++++++++-
 libavfilter/avfiltergraph.h |    9 +++++++++
 4 files changed, 70 insertions(+), 1 deletions(-)

diff --git a/libavfilter/avfilter.c b/libavfilter/avfilter.c
index 28c2599..e4e5b97 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,34 @@ int avfilter_poll_frame(AVFilterLink *link)
     return min;
 }
 
+static void swap_links(AVFilterLink *a, AVFilterLink *b)
+{
+    a->next_by_age[1] = b->next_by_age[1];
+    b->next_by_age[0] = a->next_by_age[0];
+    if (a->next_by_age[1])
+        a->next_by_age[1]->next_by_age[0] = a;
+    if (b->next_by_age[0])
+        b->next_by_age[0]->next_by_age[1] = b;
+    else if (b->graph && b->graph->oldest_sink_link == a)
+        b->graph->oldest_sink_link = b;
+    b->next_by_age[1] = a;
+    a->next_by_age[0] = b;
+}
+
+static void update_link_current_pts(AVFilterLink *link)
+{
+    if (link->cur_buf->pts == AV_NOPTS_VALUE)
+        return;
+    link->current_pts = av_rescale_q(link->cur_buf->pts, link->time_base,
+                                                         AV_TIME_BASE_Q);;
+    while (link->next_by_age[1] &&
+           link->next_by_age[1]->current_pts < link->current_pts)
+        swap_links(link, link->next_by_age[1]);
+    while (link->next_by_age[0] &&
+           link->next_by_age[0]->current_pts > link->current_pts)
+        swap_links(link->next_by_age[0], 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 +638,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 +743,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 5964397..93a70d8 100644
--- a/libavfilter/avfilter.h
+++ b/libavfilter/avfilter.h
@@ -696,6 +696,24 @@ 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.
+     */
+
+    /**
+     * Pointers to links allowing an access by age.
+     * For internal use, the exact contents may change without notice.
+     */
+    struct AVFilterLink *next_by_age[2];
 };
 
 /**
diff --git a/libavfilter/avfiltergraph.c b/libavfilter/avfiltergraph.c
index e46ace5..b5a8171 100644
--- a/libavfilter/avfiltergraph.c
+++ b/libavfilter/avfiltergraph.c
@@ -377,8 +377,9 @@ int ff_avfilter_graph_config_formats(AVFilterGraph *graph, AVClass *log_ctx)
 static void ff_avfilter_graph_config_pointers(AVFilterGraph *graph,
                                               AVClass *log_ctx)
 {
-    unsigned i, j;;
+    unsigned i, j;
     AVFilterContext *f;
+    AVFilterLink **tail = &graph->oldest_sink_link, *prev = NULL;
 
     for (i = 0; i < graph->filter_count; i++) {
         f = graph->filters[i];
@@ -386,7 +387,16 @@ static void ff_avfilter_graph_config_pointers(AVFilterGraph *graph,
             f->inputs[j]->graph = graph;
         for (j = 0; j < f->output_count; j++)
             f->outputs[j]->graph = graph;
+        if (!f->output_count) {
+            for (j = 0; j < f->input_count; j++) {
+                f->inputs[j]->next_by_age[0] = prev;
+                *tail = f->inputs[j];
+                prev = f->inputs[j];
+                tail = &prev->next_by_age[1];
+            }
+        }
     }
+    *tail = NULL;
 }
 
 int avfilter_graph_config(AVFilterGraph *graphctx, void *log_ctx)
diff --git a/libavfilter/avfiltergraph.h b/libavfilter/avfiltergraph.h
index 2c612b4..ef82da9 100644
--- a/libavfilter/avfiltergraph.h
+++ b/libavfilter/avfiltergraph.h
@@ -33,6 +33,15 @@ 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 *oldest_sink_link;
 } AVFilterGraph;
 
 /**
-- 
1.7.2.5