On Sat, Sep 13, 2014 at 09:06:56PM +0200, Clément Bœsch wrote:
> ---
> libavformat/assenc.c | 89
> +++++++++++++++++++++++++++++++++++++++++++++++++---
> 1 file changed, 85 insertions(+), 4 deletions(-)
>
> diff --git a/libavformat/assenc.c b/libavformat/assenc.c
> index 9fb9f23..acc21b9 100644
> --- a/libavformat/assenc.c
> +++ b/libavformat/assenc.c
> @@ -19,12 +19,22 @@
> * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
> USA
> */
>
> +#include "libavutil/avstring.h"
> #include "avformat.h"
> #include "internal.h"
>
> +typedef struct DialogueLine {
> + int readorder;
> + char *line;
> + struct DialogueLine *prev, *next;
> +} DialogueLine;
> +
> typedef struct ASSContext{
> unsigned int extra_index;
> int write_ts; // 0: ssa (timing in payload), 1: ass (matroska like)
> + int expected_readorder;
> + DialogueLine *dialogue_cache;
> + int cache_size;
> }ASSContext;
>
> static int write_header(AVFormatContext *s)
> @@ -60,19 +70,82 @@ static int write_header(AVFormatContext *s)
> return 0;
> }
>
> +static void purge_dialogues(AVFormatContext *s, int force)
> +{
> + int n = 0;
> + ASSContext *ass = s->priv_data;
> + DialogueLine *dialogue = ass->dialogue_cache;
> +
> + while (dialogue && (dialogue->readorder == ass->expected_readorder ||
> force)) {
> + DialogueLine *next = dialogue->next;
> + if (dialogue->readorder != ass->expected_readorder) {
> + av_log(s, AV_LOG_WARNING, "ReadOrder gap found between %d and
> %d\n",
> + ass->expected_readorder, dialogue->readorder);
> + ass->expected_readorder = dialogue->readorder;
> + }
> + avio_printf(s->pb, "Dialogue: %s\r\n", dialogue->line);
> + av_free(dialogue->line);
> + av_free(dialogue);
> + if (next)
> + next->prev = NULL;
> + dialogue = ass->dialogue_cache = next;
> + ass->expected_readorder++;
> + n++;
> + }
> + ass->cache_size -= n;
> + if (n > 1)
> + av_log(s, AV_LOG_DEBUG, "wrote %d ASS lines, cached dialogues: %d,
> waiting for event id %d\n",
> + n, ass->cache_size, ass->expected_readorder);
> +}
> +
> +static void insert_dialogue(ASSContext *ass, DialogueLine *dialogue)
> +{
> + DialogueLine *cur, *next, *prev = NULL;
> +
> + next = ass->dialogue_cache;
> + for (cur = next; cur; cur = cur->next) {
> + if (cur->readorder > dialogue->readorder)
> + break;
> + prev = cur;
> + next = cur->next;
> + }
> + if (prev) {
> + prev->next = dialogue;
> + dialogue->prev = prev;
> + } else {
> + dialogue->prev = ass->dialogue_cache;
> + ass->dialogue_cache = dialogue;
> + }
> + if (next) {
> + next->prev = dialogue;
> + dialogue->next = next;
> + }
> + ass->cache_size++;
> +}iam not sure what the typical insert vs remove statistics are but this looks like O(n^2) time to me, which might be a problem if there are millions of entries for a mixed insert + remove "lowest" data structure, theres heap sort with O(n log n) worst case, or various other options [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Democracy is the form of government in which you can choose your dictator
signature.asc
Description: Digital signature
_______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
