[FFmpeg-devel] [PATCH 1/8] lavf: add internal demuxer helpers for subtitles.

[Michael Niedermayer]

On Mon, Jun 18, 2012 at 10:56:19PM +0200, Clément Bœsch wrote:
> On Mon, Jun 18, 2012 at 07:55:04PM +0200, Michael Niedermayer wrote:
> > On Mon, Jun 18, 2012 at 07:37:08AM +0200, Reimar Döffinger wrote:
> > > On 17 Jun 2012, at 14:29, Nicolas George <nicolas.george at normalesup.org> wrote:
> > > > Le decadi 30 prairial, an CCXX, Clément Bœsch a écrit :
> > > >> 
> > > >> +static int cmp_pkt_sub(const void *a, const void *b)
> > > >> +{
> > > >> +    const int64_t t1 = ((const FFDemuxSubEntry *)a)->start;
> > > >> +    const int64_t t2 = ((const FFDemuxSubEntry *)b)->start;
> > > >> +    if (t1 == t2)
> > > >> +        return 0;
> > > >> +    return t1 > t2 ? 1 : -1;
> > > >> +}
> > > > 
> > > > The qsort function from the libc is not guaranteed to be stable. In
> > > > subtitles, the order of arrival of simultaneous events may be relevant.
> > > 
> > > Note that even if not required, that kind of thing can cause test failures, so it is always best to never use qsort in a way that gives it a choice.
> > > Also in some cases it makes sense to use your own sort function more fit for the purpose, but probably that's not the case here.
> > 
> > ive added our own qsort & merge sort to libavutil so there are some
> > choices for libc implementation independant solutions / for regression
> > tests
> > 
> 
> Thanks, I'll update the patchset soon with this. Also, should we really
> make it public?
> 
> I would propose FF_SORT() instead:
>  - it's private so we can change the implementation at some point (from
>    what you said on IRC "at the moment" it's not yet keeping the original
>    order of entries in case of equality, but it could change

theres AV_MSORT now if you need a stable sort but its half the speed
also stability aka keeping the original order is a
matter of never returning 0 for differing entries in the qsort case.


>  - not "QSORT" but "SORT" so we can change the algorithm without caring
>    about the name

you need a stable sort
someone else needs a inplace sort due to lack of memory on his embeded
device,
yet another needs a sort that is guaranteed to be reasonable speed no
matter what crafted input
and then someone needs a really fast sort that has none of these
requirements

what would that generic SORT() gurantee of these ?
and how would that be implemented ?

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Those who are best at talking, realize last or never when they are wrong.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20120618/676a20f6/attachment.asc>