[FFmpeg-devel] [mov] Fix trampling of ctts during seeks when sidx support is enabled.

[Michael Niedermayer]

On Thu, Aug 24, 2017 at 05:06:16PM -0700, Dale Curtis wrote:
> On Thu, Aug 24, 2017 at 2:27 AM, Michael Niedermayer <michael at niedermayer.cc
> > wrote:
> 
> >
> > can the insertions be done in groups instead of one at a time ?
> > so that it basically merges 2 lists (O(n)) instead of inserting
> > one at a time O(n^2)
> > ?
> > This would significantly improve the worst case while not needing
> > to change the data structures
> > (of course iam not against changing the data structures if someone wants
> > to do the work)
> >
> 
> Unfortunately this is hard / impossible to do if I understand what you're
> asking for correctly. Here's my response to the same suggestion from Rodger
> above: "We could speculatively move all entries based on the first insert
> and total entries count, but their are several conditionals in
> av_add_index_entry() which may cause a bail out and such failure would be
> unrecoverable (maybe painfully?) if we moved everything ahead of time."

hmm

maybe i misunderstand but assuming we insert a block of dummy blank
entries (without breaking monotonicity) and keep a pointer to that
block

then add entries with a av_add_index_entry()
and in case of failure remove the blank entries

this would result in the same as now and seems relativly simple
it would not need memmove and in general would not need a log n
search if each falls on the first spot of the block

or am i missing something ?





[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

When the tyrant has disposed of foreign enemies by conquest or treaty, and
there is nothing more to fear from them, then he is always stirring up
some war or other, in order that the people may require a leader. -- Plato
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20170825/c0b24c9c/attachment.sig>