+
+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;
+}