On Thu, Aug 24, 2017 at 05:06:16PM -0700, Dale Curtis wrote: > On Thu, Aug 24, 2017 at 2:27 AM, Michael Niedermayer <mich...@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
signature.asc
Description: Digital signature
_______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel