Improve amortized worst case speed of the muxers packet interleaving code

from O(packets_in_the_file) to O(num_of_streams).

Originally committed as revision 19887 to svn://svn.ffmpeg.org/ffmpeg/trunk

4 files changed, 33 insertions, 13 deletions

diff --git a/libavformat/avformat.h b/libavformat/avformat.h
index a064d76f02..1fd6ec0475 100644
--- a/libavformat/avformat.h
+++ b/libavformat/avformat.h
@@ -452,10 +452,10 @@ typedef struct AVStream {
     int probe_packets;
 
     /**
-     * Number of packets in packet_buffer for this stream when muxing.
+     * last packet in packet_buffer for this stream when muxing.
      * used internally, NOT PART OF PUBLIC API, dont read or write from outside of libav*
      */
-    int num_in_packet_buffer;
+    struct AVPacketList *last_in_packet_buffer;
 } AVStream;
 
 #define AV_PROGRAM_RUNNING 1
diff --git a/libavformat/mxfenc.c b/libavformat/mxfenc.c
index 0a44b12e09..8175a9b1cf 100644
--- a/libavformat/mxfenc.c
+++ b/libavformat/mxfenc.c
@@ -1836,6 +1836,9 @@ static int mxf_interleave_get_packet(AVFormatContext *s, AVPacket *out, AVPacket
             // purge packet queue
             while (pktl) {
                 AVPacketList *next = pktl->next;
+
+                if(s->streams[pktl->pkt.stream_index]->last_in_packet_buffer == pktl)
+                    s->streams[pktl->pkt.stream_index]->last_in_packet_buffer= NULL;
                 av_free_packet(&pktl->pkt);
                 av_freep(&pktl);
                 pktl = next;
@@ -1844,6 +1847,7 @@ static int mxf_interleave_get_packet(AVFormatContext *s, AVPacket *out, AVPacket
                 last->next = NULL;
             else {
                 s->packet_buffer = NULL;
+                s->packet_buffer_end= NULL;
                 goto out;
             }
             pktl = s->packet_buffer;
@@ -1852,6 +1856,10 @@ static int mxf_interleave_get_packet(AVFormatContext *s, AVPacket *out, AVPacket
         *out = pktl->pkt;
         //av_log(s, AV_LOG_DEBUG, "out st:%d dts:%lld\n", (*out).stream_index, (*out).dts);
         s->packet_buffer = pktl->next;
+        if(s->streams[pktl->pkt.stream_index]->last_in_packet_buffer == pktl)
+            s->streams[pktl->pkt.stream_index]->last_in_packet_buffer= NULL;
+        if(!s->packet_buffer)
+            s->packet_buffer_end= NULL;
         av_freep(&pktl);
         return 1;
     } else {
diff --git a/libavformat/oggenc.c b/libavformat/oggenc.c
index 2bd8e0d49f..9ab1ac0aff 100644
--- a/libavformat/oggenc.c
+++ b/libavformat/oggenc.c
@@ -261,6 +261,12 @@ static int ogg_interleave_per_granule(AVFormatContext *s, AVPacket *out, AVPacke
             OGGStreamContext *ogg = s->streams[out->stream_index]->priv_data;
             ogg->eos = 1;
         }
+        if(!s->packet_buffer)
+            s->packet_buffer_end= NULL;
+
+        if(s->streams[out->stream_index]->last_in_packet_buffer == pktl)
+            s->streams[out->stream_index]->last_in_packet_buffer= NULL;
+
         av_freep(&pktl);
         return 1;
     } else {
diff --git a/libavformat/utils.c b/libavformat/utils.c
index ffaf159fbf..d1d98b0ffb 100644
--- a/libavformat/utils.c
+++ b/libavformat/utils.c
@@ -2657,25 +2657,30 @@ void ff_interleave_add_packet(AVFormatContext *s, AVPacket *pkt,
     pkt->destruct= NULL;             // do not free original but only the copy
     av_dup_packet(&this_pktl->pkt);  // duplicate the packet if it uses non-alloced memory
 
-    if(!s->packet_buffer_end || compare(s, &s->packet_buffer_end->pkt, pkt)){
+    if(s->streams[pkt->stream_index]->last_in_packet_buffer){
+        next_point = &(s->streams[pkt->stream_index]->last_in_packet_buffer->next);
+    }else
         next_point = &s->packet_buffer;
-        while(*next_point){
-            if(compare(s, &(*next_point)->pkt, pkt))
-                break;
+
+    if(*next_point){
+        if(compare(s, &s->packet_buffer_end->pkt, pkt)){
+            while(!compare(s, &(*next_point)->pkt, pkt)){
             next_point= &(*next_point)->next;
         }
+            goto next_non_null;
     }else{
         next_point = &(s->packet_buffer_end->next);
-        assert(!*next_point);
+        }
     }
-    this_pktl->next= *next_point;
+        assert(!*next_point);
 
-    if(!*next_point)
         s->packet_buffer_end= this_pktl;
+next_non_null:
 
-    *next_point= this_pktl;
+    this_pktl->next= *next_point;
 
-    s->streams[pkt->stream_index]->num_in_packet_buffer++;
+    s->streams[pkt->stream_index]->last_in_packet_buffer=
+    *next_point= this_pktl;
 }
 
 int ff_interleave_compare_dts(AVFormatContext *s, AVPacket *next, AVPacket *pkt)
@@ -2701,7 +2706,7 @@ int av_interleave_packet_per_dts(AVFormatContext *s, AVPacket *out, AVPacket *pk
     }
 
     for(i=0; i < s->nb_streams; i++)
-        stream_count+= !!s->streams[i]->num_in_packet_buffer;
+        stream_count+= !!s->streams[i]->last_in_packet_buffer;
 
     if(stream_count && (s->nb_streams == stream_count || flush)){
         pktl= s->packet_buffer;
@@ -2711,7 +2716,8 @@ int av_interleave_packet_per_dts(AVFormatContext *s, AVPacket *out, AVPacket *pk
         if(!s->packet_buffer)
             s->packet_buffer_end= NULL;
 
-        s->streams[out->stream_index]->num_in_packet_buffer--;
+        if(s->streams[out->stream_index]->last_in_packet_buffer == pktl)
+            s->streams[out->stream_index]->last_in_packet_buffer= NULL;
         av_freep(&pktl);
         return 1;
     }else{