[FFmpeg-devel] [PATCH 3/4] avformat/flvenc: Use array instead of linked list for index

[Andreas Rheinhardt]

Using a linked list had very much overhead (the pointer to the next
entry increased the size of the index entry struct from 16 to 24 bytes,
not to mention the overhead of having separate allocations), so it is
better to (re)allocate a continuous array for the index.

Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt at gmail.com>
---
 libavformat/flvenc.c | 58 +++++++++++++++-----------------------------
 1 file changed, 19 insertions(+), 39 deletions(-)

diff --git a/libavformat/flvenc.c b/libavformat/flvenc.c
index 0e6c66a5ff..a2bd791c59 100644
--- a/libavformat/flvenc.c
+++ b/libavformat/flvenc.c
@@ -74,7 +74,6 @@ typedef enum {
 typedef struct FLVFileposition {
     int64_t keyframe_position;
     double keyframe_timestamp;
-    struct FLVFileposition *next;
 } FLVFileposition;
 
 typedef struct FLVContext {
@@ -108,9 +107,9 @@ typedef struct FLVContext {
     int acurframeindex;
     int64_t keyframes_info_offset;
 
-    int64_t filepositions_count;
     FLVFileposition *filepositions;
-    FLVFileposition *head_filepositions;
+    size_t filepositions_allocated;
+    int64_t filepositions_count;
 
     AVCodecParameters *audio_par;
     AVCodecParameters *video_par;
@@ -549,27 +548,19 @@ static void flv_write_codec_header(AVFormatContext* s, AVCodecParameters* par, i
 
 static int flv_append_keyframe_info(AVFormatContext *s, FLVContext *flv, double ts, int64_t pos)
 {
-    FLVFileposition *position = av_malloc(sizeof(FLVFileposition));
-
-    if (!position) {
-        av_log(s, AV_LOG_WARNING, "no mem for add keyframe index!\n");
-        return AVERROR(ENOMEM);
-    }
-
-    position->keyframe_timestamp = ts;
-    position->keyframe_position = pos;
-
-    if (!flv->filepositions_count) {
-        flv->filepositions = position;
-        flv->head_filepositions = flv->filepositions;
-        position->next = NULL;
-    } else {
-        flv->filepositions->next = position;
-        position->next = NULL;
-        flv->filepositions = flv->filepositions->next;
+    if (flv->filepositions_count >= flv->filepositions_allocated) {
+        void *pos = av_realloc_array(flv->filepositions,
+                                     2 * flv->filepositions_allocated + 1,
+                                     sizeof(*flv->filepositions));
+        if (!pos) {
+            av_log(s, AV_LOG_WARNING, "No memory for keyframe index\n");
+            return AVERROR(ENOMEM);
+        }
+        flv->filepositions = pos;
+        flv->filepositions_allocated = 2 * flv->filepositions_allocated + 1;
     }
 
-    flv->filepositions_count++;
+    flv->filepositions[flv->filepositions_count++] = (FLVFileposition){ pos, ts };
 
     return 0;
 }
@@ -784,7 +775,7 @@ static int flv_write_trailer(AVFormatContext *s)
     int64_t cur_pos = avio_tell(s->pb);
 
     if (build_keyframes_idx) {
-        FLVFileposition *newflv_posinfo, *p;
+        FLVFileposition *flv_posinfo = flv->filepositions;
 
         avio_seek(pb, flv->videosize_offset, SEEK_SET);
         put_amf_double(pb, flv->videosize);
@@ -809,28 +800,17 @@ static int flv_write_trailer(AVFormatContext *s)
         avio_seek(pb, flv->keyframes_info_offset, SEEK_SET);
         put_amf_string(pb, "filepositions");
         put_amf_dword_array(pb, flv->filepositions_count);
-        for (newflv_posinfo = flv->head_filepositions; newflv_posinfo; newflv_posinfo = newflv_posinfo->next) {
-            put_amf_double(pb, newflv_posinfo->keyframe_position + flv->keyframe_index_size);
+        for (i = 0; i < flv->filepositions_count; i++) {
+            put_amf_double(pb, flv_posinfo[i].keyframe_position + flv->keyframe_index_size);
         }
 
         put_amf_string(pb, "times");
         put_amf_dword_array(pb, flv->filepositions_count);
-        for (newflv_posinfo = flv->head_filepositions; newflv_posinfo; newflv_posinfo = newflv_posinfo->next) {
-            put_amf_double(pb, newflv_posinfo->keyframe_timestamp);
+        for (i = 0; i < flv->filepositions_count; i++) {
+            put_amf_double(pb, flv_posinfo[i].keyframe_timestamp);
         }
 
-        newflv_posinfo = flv->head_filepositions;
-        while (newflv_posinfo) {
-            p = newflv_posinfo->next;
-            if (p) {
-                newflv_posinfo->next = p->next;
-                av_free(p);
-                p = NULL;
-            } else {
-                av_free(newflv_posinfo);
-                newflv_posinfo = NULL;
-            }
-        }
+        av_freep(&flv->filepositions);
 
         put_amf_string(pb, "");
         avio_w8(pb, AMF_END_OF_OBJECT);
-- 
2.20.1